Vpropel VIT | POD | 11/05/2020 | Skipping Stones | 11

Question(skipping_stones).txt

Skipping Stones
Yogee and his friends are playing skipping stones.
 Each stone has a value which represents the maximum number of stones you can jump from that particular stone.
 It was yogee’s turn. Given the value of every stones help him to find the minimum number of jumps required to
 reach to the last stone provided that he starts from the first stone.

Assume you can always reach the last stone

Example:-

Consider that stones have the following value

[2,3,1,3,4]

Case1:-

He starts from the first index. a[0]=2,So he can at max reach a[2], a[2]=1 So he can only jump to a[3].a[3]=3
 So he can reach end from here with a jump.

Total number of jumps =3

Case 2:-

From a[0] he reaches a[1] as he can at maximum jump 2 stones. a[1] is 3,
So he can jump 3 stones and can directly reach the end with a jump.

Total number of jumps =2

2 is the expected answer.

Input format:-

Total number of stones(n)

Next n lines-Value of stones

Output format:-

Minimum number of jumps required.

Constraints:-

0<=number of stones<=100000

Rank.txt

1	19BCE1401	S VAIBHAVE
2	19BLC1055	SUNIL KUMAR GV
3	19BCE1376	VIKASH SUNIL
4	19BAI1151	PRANAV BALAJI
5	19BCE2643	SANDESH DHUNGANA
6	19BCE1415	V.RAGHAV ANAND
7	19BAI1035	S.O.NARENDRAN
8	19BCE1207	PRANJAL SINGH
9	19BCE0106	NIKITA SHARMA
10	19BDS0017	RAMADUGULA NAGA SAI VENKAT
11	19BCI0016	CHIRANJEET SINGH
12	19BCE1492	P.K. AMUDHINI
13	19BEC1212	SUJITH K P
14	19BDS0078	ANIRUDH MISHRA
15	19BCE2642	GUNJAN RAJ TIWARI

skipping_stones.c

#include <stdio.h> 
#include<limits.h>
  
int minJumps(int arr[], int n) 
{ 
    int *jumps=(int*)calloc(n,sizeof(int));   // Note that in c++, we can simply initialize -- int jumps[n]={0}; but not in C
    int min;                                   // moreover, dynamically allocated array is intialized to 0 in C/C++ 
    jumps[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--)
    { 
            min = INT_MAX; 
            for (int j = i + 1; j < n && arr[i]>=j-i; j++) 
            { 
                if (min > jumps[j]) 
                    min = jumps[j]; 
            } 
  
            if (min != INT_MAX) 
                jumps[i] = min + 1; 
            else
                jumps[i] = min; // or INT_MAX 
    } 
  
    return jumps[0]; 
}
  
int main() 
{ 
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);
    printf("%d",minJumps(arr, n)); 
    return 0; 
} 

skipping_stones.cpp

#include <iostream> 
#include<climits>
using namespace std; 
  
int minJumps(int arr[], int n) 
{ 
    int jumps[n]={0};
    int min; 
    jumps[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) 
    { 
            min = INT_MAX; 
            for (int j = i + 1; j < n && arr[i]>=j-i; j++) 
            { 
                if (min > jumps[j]) 
                    min = jumps[j]; 
            } 
  
            if (min != INT_MAX) 
                jumps[i] = min + 1; 
            else
                jumps[i] = min; // or INT_MAX 
    } 
  
    return jumps[0]; 
}
  
int main() 
{ 
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout << minJumps(arr, n); 
    return 0; 
}