Given an array of Integers arr, from an element val = arr[i], you can go to element i to i+val. If val is zero, you cannot move forward. find the least selection to reach end of the array. example: 1 3 5 8 9 2 6 7 6 8 9 @index 0, can go to 1 @index 1, can go to 4. if index 3 and 4 choosen, it will reach to end frm there only. Give an algorithm and program. This can be solved with greedy aproach. Assume we are at index i, So For all i ..to i+a[i] index check for the max value value of k+a[k], where i We can prove the correctness of this . If k+a[k] having maximum value then any value except the k in range of i to i+a[i] will be less than range reachable by k. So by choosing k, you still can choose the option available with other indexs.
Collection of Interview Question on Data structure, Algorithm, Java, C++ and more