-2

Given an array of N integers arr[] where each element represents the max length of the jump that can be made forward from that element. Find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then you cannot move through that element.

Note: Return -1 if you can't reach the end of the array.

My code --

int minJumps(int arr[], int n){
        int i=0, count=0;
        while(i<n-1){ 
            if(arr[i]==0){
                return -1;
            }
            i+=arr[i];
            count++;
        }
        return count;
    }

Input:
n=10
arr[ ]=2 3 1 1 2 4 2 0 1 1

So here first jump goes from to 2 to 1, second jump goes from 1 to 1, third jump goes from 1 to 2, fourth jump goes from to 2 to 2, fifth jump goes from 2 to 1 and last sixth jump goes from 1 to 1. So I got 6 jumps. But the answer is 4 jumps.

If we start particularly from the first element, we can only have one way of going na?
So I think my understanding is wrong, please explain anyone.

timrau
  • 22,578
  • 4
  • 51
  • 64
doubtttttttttttttt
  • 3
  • 1
  • Tip: In C++ it's far more convenient to pass around `const std::vector&`. – tadman Oct 07 '22 at 06:11
  • 1
    When doing your "jumps" also think about the loop condition `i < n - 1`. I suggest you take some time to step through your code line by line in a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems), while monitoring variables and their values, to see what really happens. – Some programmer dude Oct 07 '22 at 06:16
  • 1
    I hope this is for an algorithms class. Notice that you are given a _maximum_ jump size. You can always jump _less_ than the allowed maximum. Try this element sequence: 0 1 4 5 9. That’s four jumps. You should expect your solution to be _recursive_. – Dúthomhas Oct 07 '22 at 06:28
  • 1
    The algorithm is not expected to jump blindly as far it can but smartly. For example like first jump from 2 to 3, second jump from 3 to 2, third jump from 2 to 4 and final jump from 4 to last 1 – Öö Tiib Oct 07 '22 at 06:41
  • 1
    This is a graph problem in disguise. Observe that any walk from start to end with k jumps and total sum s of jump distances will always satisfy k+s=n. So any path that maximises s will minimise k, which is what you want. If you construct a graph you can use standard algorithms like bellman-ford or dijkstra if you invert the edge weights. – bitmask Oct 07 '22 at 07:02

1 Answers1

1

There are multiple ways through the array.

The one you described is:

  2  1 1  2   2  1   6 jumps
┌───┬─┬─┬───┬───┬─┐
2 3 1 1 2 4 2 0 1 1

But you can also do:

 1   3    2   2  1   5 jumps
┌─┬─────┬───┬───┬─┐
2 3 1 1 2 4 2 0 1 1
↑
jump 1 forward, not 2

You can find an optimal solution as:

 1   3   1   4        4 jumps
┌─┬─────┬─┬───────┐
2 3 1 1 2 4 2 0 1 1

For any given array, there may be more than one optimal solution.

The trick is to explore them all

Every time you have a decision to make, make them all.

For example, given our first jump of 2, we could also choose to jump 1. Whenever you have a choice like this you will need to build yourself a recursive solution.

Conveniently, you only need to return the minimal number of jumps. You do not actually have to return the jump path. So your function can be written to return exactly that information:

int minJumps( int array[], int size )

The thing that will change is your starting index. You can add that as an additional argument:

int minJumps( int array[], int size, int index = 0 )

Or you can just adjust the array value when you recurse:

  ... = minJumps( array + n, size - n );

Either way you do the same thing: index a smaller and smaller array.

For example, you can easily answer for this array:

1     zero jumps. (You are at the end of the array)

And this array:

0     zero jumps. (You are at the end of the array)

How about this array:

1 1

Or this array:

5 1

The answer to both is 1 jump, because if we choose a jump-by-1 we get the result of 0 == end of array.

For this array, though:

0 1

The answer is no jumps.

So can you answer for this array?

1 1 1

Or this array?

1 5 1

How about this array?

1 0 1

Aaaannnd... how about these arrays?

2 1 1
2 0 1

The decision factor here is where recursion is useful. Each time you recurse you are working on a smaller array. For the penultimate example, I can get to the end of the array with two possible paths:

┌───┐   1 jump
2 1 1   2 straight to end works. return 1 jump

┌─┬─┐   2 jumps
2 1 1   recurse to get 1 jump for the end of the array. return that + 1.
↑
decision point

But there is only one way with:

┌───┐   1 jump
2 0 1   2 straight to end works. return 1 jump

┌─┬─┐   no jumps
2 0 1   recurse to get -1 for the end of the array.
↑
decision point

With both of these examples we see that the minimum number of jumps is if we choose the jump-by-2.

So, each time you have a decision, take them all. Ignore the bad ones (stuff that returns -1) and choose the smallest number of jumps every time.

Oh, don’t forget to not jump past the end of the array. So

5 1
↑
decision point

Since the array is size 2, you cannot jump more than 1 forward.

Putting it together

Here are the conditions given you:

  • You have one element in the array. Return 0.
  • The current element is zero. Return -1. (Cannot advance.)
  • The current element is n. Recurse for each 1,2,...,n, making sure that you do not exceed the bounds of the array. Return the smallest value you got from your recursive calls.

That’s it! It takes some time to work your mind around recursion, but the main idea is to solve for the simplest case (a single element array), then solve for that with one more element. Or, if I can do a thing to the first element of an array in relation to the rest of the array, then I can do it to the whole array.

Edit: I have written this answer assuming that you have not been given instruction about Graph Theory. If you have, then do as bitmask instructs and look at the algorithms you have been studying. At least one of them will apply to traversing this graph.

Dúthomhas
  • 8,200
  • 2
  • 17
  • 39