Given an array of Integers, if u are on ith element u can make max arr jumps. If i am at an element with value zero, i cannot move forward. find the least selection to reach end of the array.

/*
  Algo:
      Lets define a function called hop which is number of steps required to reach the end of array from the given position, So

      hop(i) = INT_MAX if a[i] == 0
      hop(i) = 1 + min(hop(j)  where j is from i + 1 to i + a[i]

      hop(0) is the required answer
*/

#include <stdio.h>
#include <limits.h>

int minhops(int a[], int n) {

int hop[n] ;

int i = n;

while(i--) {

if(a[i] == 0)
hop[i] = INT_MAX;

else {

if(i + a[i] >= n)
hop[i] = 1;
else {

int j, min = INT_MAX;

for(j = i + a[i]; j > i; --j){

if(hop[j] < min)
min = hop[j];
}

hop[i] = min + 1;
}
}

}


return hop[0];
}


int main() {

int a[] = {1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
int n = minhops(a, 11);

if(n != INT_MAX)
printf("%d\n", minhops(a, 11));


return 0;
}
Advertisements

One thought on “Given an array of Integers, if u are on ith element u can make max arr jumps. If i am at an element with value zero, i cannot move forward. find the least selection to reach end of the array.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s