Friday, July 1, 2022
HomeWordPress DevelopmentExamine if final index might be reached by leaping atmost soar in...

Examine if final index might be reached by leaping atmost soar[i] in every place


View Dialogue

Enhance Article

Save Article

Like Article

Given an array of jumps[] of size N, the place every aspect denotes the utmost size of a soar ahead from every index. The duty is to seek out whether it is potential to achieve the final index.

Examples:

Enter: arr[] = {2, 3, 1, 1, 4}
Output: True
Clarification: Potential methods to achieve final index are:
(0->2->3->4), (0->2->3->1->1->4), (0->2->3->1->4) and (0->2->1->1->4).

Enter:  arr[] = {3, 2, 1, 0, 4}
Output: False
Clarification: There is no such thing as a approach to attain final index.

 

Method: The thought to resolve the issue is as talked about under:

We all know that the final index is all the time reachable from itself. Assume that vacation spot is leaping in the direction of the primary index. So the essential job is to test if the final potential index is reachable from the present index and replace the final potential index accordingly.

Comply with the under steps to resolve the issues:

  • Keep a variable LastAccuratePos (initialized to N-1) from which we are able to attain the final place.
  • Now begin iterating the enter array jumps[] from the correct (second final place) to left.
    • In every iteration, calculate FurthestJump which is the summation of the index and the worth at that index (i.e jumps[i]+i).
    • Examine if FurthestJump is bigger than or equal to LastAccuratePos. If sure, then we’ll replace the worth of LastAccuratePos with the present index.
  • After the iteration, test if LastAccuratePos is 0 then return True, else return False.

Under is the implementation of the above strategy.

C++14

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

bool isPossibleLastIndex(int* jumps, int& n)

{

    

    

    int LastAccuratePos = n - 1, FurthestJump = 0;

  

    for (int i = n - 2; i >= 0; i--) {

  

        

        FurthestJump = jumps[i] + i;

  

        

        

        

        if (FurthestJump >= LastAccuratePos)

            LastAccuratePos = i;

    }

  

    

    return LastAccuratePos == 0;

}

  

int fundamental()

{

    int jumps[] = { 2, 3, 1, 1, 4 };

    int N = sizeof(jumps) / sizeof(jumps[0]);

  

    

    if (isPossibleLastIndex(jumps, N))

        cout << "True";

    else

        cout << "False";

  

    return 0;

}

Time Complexity: O(N)
Auxiliary House: O(1)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments