Menu
Start with an array A of positive numbers. Start at index 0. From index i, you can move to index i+x for any x <= A[i]. The goal is to find the minimum number of moves needed to get to the end of the array.
Here's an example:
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
If you always go as far as possible in each move, then this is what you get:
0 , 2 , 3 , 5 , 7
This takes 4 moves. But you can get through it faster by doing it this way
0 , 1 , 4 , 7
This only takes 3 moves.
I thought about this for a bit and did the first thing I thought of, but after thinking for a few more days, I still don't know how to do it any better.
Here's my idea. Start at the end of the array and keep track of the minimum number of moves from some position to the end. So for the example, moves[7] = 0 because it's the end already. Then moves[6] = 1 because it takes one move to get to the end. My formula is
moves[i] = 1 + min(moves[i+1], moves[i+2], ... , moves[i+A[i]])
By the time I get to the beginning, I know the number of moves.
So this is O(n^2) which is okay I guess, but probably there is a faster way?
571
Sequential search is the best that we can do when trying to find a value in an unsorted array. 1 But if the array is sorted in increasing order by value, then we can do much better. We use a process called binary search.
Which is the fastest search algorithm for unsorted array? If the array is not sorted then you have to search for the element by iteration ,linear search . There is no better way than O(n).
Negative base case : if maximum length of any jump possible from any current position is equal to zero, this means that there is no way possible with which we can reach the end of the given array as we cannot move even a single position from our current position.
Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array. Element − Each item stored in an array is called an element.
Since you can chose any x in [1,A[i]] I guess there is a pretty simple solution :
start at 0:
select the next reachable element from which you can reach the farther element. i.e chose i that maximize i+A[i+x] for x in [1,A[i]]
until you arrive at the end of the list.
Example:
{2 , 4 , 1 , 2 , 3 , 2 , 4 , 2}
start at 0
from 0 you can get to 1 or to 2:
therefore max(0+A[0+x]) is for i = 1
chose 1 from 1 you can get to 2 3 4:
therefore max(1+A[1+x]) is for i = 4
chose 4
you can reach 7
stop
the resulting list is :
0,1,4,7
As explained in my comments I think it's O(N), because from i you reach i+x+1 in at least 2*x operations.
'Pseudo' proof
You start at 0 (it's optimal)
then you select i that maximize(0+A[0+x]) (i.e that maximize the reachability for the next element)
from that i you can reach any other element that is reachable from all other elements reachable from 0 (it's a long sentence, but it means : who can do more, can do less, therefore if i is not optimal,it's as good as optimal)
So i is optimal
then following step by step this reasoning, it proves the optimality of the method.
If someone knows how to formulate that more mathematically, feel free to update it.
161
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
