Minimum number of jumps

QUESTION

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return 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.\n\nInput: \nThe first line contains an integer T, depicting total number of test cases. \nThen following T lines contains a number n denoting the size of the array.\nNext line contains the sequence of integers a1,a2,…,an.\n\nOutput:\nEach separate line showing the minimum number of jumps. If answer is not possible print -1.\n\nConstraints:\n1<=T<=30\n1<=N<=100\n0<=a[N]<=100.

“TESTCASE_1”: “1\n11\n1 3 5 8 9 2 6 7 6 8 9\n###—###SEPERATOR—###—\n3”, “TESTCASE_2”: “1\n11\n2 4 6 1 3 5 4 6 7 8 9\n###—###SEPERATOR—###—\n3”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <bits/stdc++.h>
using namespace std;

void minJumpRequired(int arr[],int n){
    int minJmp[n];
    int jmpArr[n];
    bool flag = true;
    minJmp[0]=0;
    for(int i=1;i<n;i++){
        minJmp[i]=INT_MAX;
    }
    for(int i=1;i<n && flag;i++){
        flag = false;
        for(int j=0;j<i;j++){
            if(j+arr[j]>=i)
            {   
                flag = true;
                if(minJmp[j]+1 < minJmp[i])
                {
                    minJmp[i]=minJmp[j]+1;
                    jmpArr[i]=j;
                }
            }
        }
    }
    if(flag)
    cout<<minJmp[n-1]<<endl;
    else
    cout<<-1<<endl;
}

int main() {
	//code
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i=0;i<n;i++)
	    cin>>arr[i];
	    
	    minJumpRequired(arr,n);
	}
	return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro