Given an array of N integers arr[] where each element represents the maximum length of the jump that can be made forward from that element. This means if arr[i] = x, then we can jump any distance y such that y ≤ x. 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.
Input: N = 11 arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} Output: 3 Explanation: First jump from 1st element to 2nd element with value 3. Now, from here we jump to 5th element with value 9, and from here we will jump to the last.
Input : N = 6 arr = {1, 4, 3, 2, 6, 7} Output: 2 Explanation: First we jump from the 1st to 2nd element and then jump to the last element.
My code :
class Solution{
public:
int minJumps(int arr[], int n){
// Your code here
int jump=0;
int count=0;
for(int i=2;i<=n;i++){
if(arr[i]%i==0){
count++;
if(arr[i]!=i){
count++;
}
}
if(count==2){
jump++;
}
}
return jump;
}
};
Can someone explain what is wrong with this code?
As in the question, it asks us to jump to specific prime numbers in the array and we need to count the number of jumps and return it as an answer.
My approach:
First I needed to find the prime numbers. So I looped through the array. for(int i=2;i<=n;i++) here n is the size of the array.
If the arr[i]%i==0 we enter into the if code block and increase count by 1 which was initialized to 0 before.
I aain check for the condition that arr[i]!=0 then we need to increase countby1, since arr[i] would have been included otherwise in the first place.
I check if the count is 2, it is prime and i increase the jump by 1 which was initialized to zeo before.
I return jump. But none of the 144 test cases were passed with this solution :(
Please help..
You need to solve this problem working backwards from the end. You need to create an array the same size as the input array to hold your jump counts.
Consider the last element. The jump count from here is 0, so we store 0 in the final element of our jump array.
Now, back up one. For every possible jump we can make, what would be the jump count after we did that jump? In this case, there's only one element beyond us, and that element is 0, so the best jump count from here is 1.
Repeat that. For every cell in reverse order, find the smallest count in the jump array for every jump we can make, add 1, and store that in the array. When you're done, the 0th entry in the jump array is the answer.
Here is the solution in Python:
class Solution:
def minJumps(self, arr, n):
mins = [0] * n
for i in range(n-2, -1, -1):
v = arr[i]
mins[i] = 1 + min(mins[i+1:i+v+1])
print(mins)
return mins[0]
print(Solution().minJumps([1,3,5,8,9,2,6,7,6,8,9], 11))
print(Solution().minJumps([1,4,3,2,6,7], 6))
And here is the output:
[3, 2, 2, 1, 1, 2, 1, 1, 1, 1, 0]
3
[2, 1, 1, 1, 1, 0]
2