There is a greedy solution discussion about this approach. I don't have a
formal proof for this.
Any counter example will be helpful.
at every place 'k' .. do the following.
--> find max ( a[k+i]+i ) where 1 <= i <= a[i]
for the given example:
A = {4 0 0 3 6 5 4 7 1 0 1 2}
initially a 4, the loop will be.
0+1,0+2,3+3,6+4 -- 10 is max. jump to 6.
now at 6. (since, you can't reach end.)
5+1, 4+2, 7+3, 1+4, 0+5, 1 + 6, ==> 10 is max. jump to 7.
make another step. (but you can reach the end.) so jump to last.
this is greedy approach.. and a linear time soultion.
On Monday, 9 July 2012 09:32:08 UTC-4, Akshat wrote:
>
> Given an array A and the elements stored in an array denotes how much jump
> an element can make from that array position. For example there is an array
> A = {4 0 0 3 6 5 4 7 1 0 1 2}
>
> Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You
> are stuck if you end up at 0.
> You have to output the minimum number of jumps that can be made from
> starting position to end position of an array.
>
> --
>
>
> Akshat Sapra
> Under Graduation(B.Tech)
> IIIT-Allahabad(Amethi Campus)
> *--------------------------------------*
> sapraaks...@gmail.com
> akshatsapr...@gmail.com
> rit20009008@ <rit20009...@gmail.com>iiita.ac.in
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
