Two test case fail in minimum jump prolem

#1

https://ide.codingblocks.com/s/122132 minimum jump problem only two test case passed
question link https://hack.codingblocks.com/app/contests/969/p/1088

#2

@bishtmanish786 Please copy the problem statement and paste it over here. I am not able to access the question.

#3

@pratyush63 Given an array of integers where each element represents the max number of steps that can be made forward from that element. Print the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.

Input Format
n, size of array Ai, array elements

Constraints
1<=n<=5000 1<=Ai<=10^5

Output Format
Number of minimum jumps

Sample Input
11
1 3 5 8 9 2 6 7 6 8 9
Sample Output
3

#4

@pratyush63 sir i have sent you question related to my doubt

#5

@bishtmanish786 Why are you initializing each jump element with 1000? I think that may create a problem. Also for the cases where you cannot reach the end of the array as in 1 0 1 4 2 1, your code is printing 1000.

Simply do something like this:
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
// jumps[n-1] will hold the result
int *jumps = new int[n];
int i, j;

if (n == 0 || arr[0] == 0)  
    return INT_MAX;  

jumps[0] = 0;  

// Find the minimum number of jumps to reach arr[i]  
// from arr[0], and assign this value to jumps[i]  
for (i = 1; i < n; i++)  
{  
    jumps[i] = INT_MAX;  
    for (j = 0; j < i; j++)  
    {  
        if (i <= j + arr[j] && jumps[j] != INT_MAX)  
        {  
            jumps[i] = min(jumps[i], jumps[j] + 1);  
            break;  
        }  
    }  
}  
return jumps[n-1];

}

#6

@pratyush63 sir you initialize jumps[i] = INT_MAX; similarly i also initailize my jump arr with 1000;
because initially all step are infinitly away

#7

But you cannot consider 1000 as INT_MAX as according to constraints 1<=Ai<=10^5

#8

what will be ans for your test case 1 0 1 4 2 1,

#9

@pratyush63 yeah sir i understood but what would be ans of 1 0 1 4 2 1

#10

It is not clearly mentioned in the question what exactly the output should be for such case. But according to the code i have given it will print the value of INT_MAX. The similar question in the challenges section of your course had " Hint - If N==0 you can never move forward, your return INT_MAX (Infinity). " mentioned in the problem .statement

#11

https://ide.codingblocks.com/s/122448 sir this code is working fine all test case are passed
can you tell me
how to initailize every element of an array by int_max in a single line without loop

#12

Let it be done by the loop itself. If you had to initialize it with 0 or -1 then memset could have been used.

#13

thanks sir you :relaxed:

1 Like