Question

write a code for given an array of integers where wach element represents the maximum number of jumps to reach the end of the array(starting from the first element) if an element O,then no jump can be made from that element if it is not possible to reach the end then output in c

Answer 1

C Code

#include

int max(int a, int b) { return (a > b)? a: b; }

// This function will give minimum number of jumps to reach end of the array
int minJumps(int arr[], int n)
{

   // The number of jumps needed to reach the starting index is 0
   if (n <= 1)
       return 0;

   // Return -1 if not possible to jump
   if (arr[0] == 0)
       return -1;

// initialization
   int maxIndex = arr[0]; // stores all time the maximal reachable index in the array.
   int stepSize = arr[0];   // stores the number of steps
   int jump =1;//stores the number of jumps
   int i=1;
   for (i = 1; i < n; i++)
   {
       // Check if we have reached the end of the array
       if (i == n-1)
           return jump;

      // updating maxIndex
       maxIndex = max(maxIndex, i+arr[i]);

       // we use a stepSize to get to the current index
       stepSize--;

       // If no further steps left
       if (stepSize == 0)
       {
          // we must have used a jump
           jump++;

           // Check if the current index/position or lesser index
           // is the maximum index point from the previous indexes
           if(i >= maxIndex)
               return -1;

           // make the steps to the amount
           // of steps to reach maxIndex from position i.
           stepSize = maxIndex - i;
       }
   }

   return -1;
}

int main()
{
   int arr[]={3, 3, 5, 6, 0, 2, 6, 7, 6, 8, 9};
   int size = sizeof(arr)/sizeof(int);

   // Calling the minJumps function
   printf("Minimum number of jumps to reach end is %d ", minJumps(arr,size));
   return 0;
}

Input

Output