fork download
copy 
  1. // C++ program for Minimum number
  2. // of jumps to reach end
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. int min(int x, int y) { return (x < y) ? x : y; }
  9.  
  10. // Returns minimum number of jumps
  11. // to reach arr[n-1] from arr[0]
  12.  
  13. int minJumps(int arr[], int n)
  14. {
  15.  
  16.     // jumps[n-1] will hold the result
  17.  
  18.     int* jumps = new int[n];
  19.  
  20.     int i, j;
  21.  
  22.  
  23.     if (n == 0 || arr[0] == 0)
  24.  
  25.         return INT_MAX;
  26.  
  27.  
  28.     jumps[0] = 0;
  29.  
  30.  
  31.     // Find the minimum number of jumps to reach arr[i]
  32.  
  33.     // from arr[0], and assign this value to jumps[i]
  34.  
  35.     for (i = 1; i < n; i++) {
  36.  
  37.         jumps[i] = INT_MAX;
  38.  
  39.         for (j = 0; j < i; j++) {
  40.  
  41.             if (i <= j + arr[j] && jumps[j] != INT_MAX) {
  42.  
  43.                 jumps[i] = min(jumps[i], jumps[j] + 1);
  44.  
  45.                 break;
  46.  
  47.             }
  48.  
  49.         }
  50.  
  51.     }
  52.  
  53.     return jumps[n - 1];
  54. }
  55.  
  56. // Driver code
  57.  
  58. int main()
  59. {
  60.  
  61.     int arr[] = { 1, 3, 6, 1, 0, 9 };
  62.  
  63.     int size = sizeof(arr) / sizeof(int);
  64.  
  65.     cout << "Minimum number of jumps to reach end is "
  66.  
  67.          << minJumps(arr, size);
  68.  
  69.     return 0;
  70. }
  71.  
  72. // This is code is contributed by rathbhupendra
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum number of jumps to reach end is 3
https://ideone.com/1oBFxN
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!