Want a better approach

#1

can you please check my code and tell if there is a better approach to solve this question? my code has a complexity of 10^5.

#2

Hey @Akshita99 hope you are doing well ,
The current complexity of your solution is O(n^2) and the complexity of this solution can be reduced to O(n).
Although the O(N) solution is a little non intuitive at first .
Let me know if you want to know the algorithm as well .

Hope it helps :blush: .
If your doubt is now resolved please mark it as resolved and rate me accordingly .
Else you can further questions here .
Thankyou

#3

please give a little hint on the algo too

#4

What you can do is to keep a track of maxReach for every element ( i+Arr[i]) . If maxReach at any point is to the end of the array then we have found the ans .

We will not want to count those elements whose maxreach is not greater than the maxreach of current element .
So first we traverse the array and see at every element if the maxReach of the elements is greater than the current maxreach after that once our currect maxreach is reached we increase the jump by 1.

Might be a little difficult to understad . If you want the code you can message me personally . Thankyou :slight_smile:

#5

please tell the problem in my code. https://ide.codingblocks.com/s/327619

#6

@Akshita99 I have texted you on chat have a look there

#7

thank you sir, I got it :blush:

1 Like