Minimum number of jumps required to sort the given array in ascending order | C ++ program for the above approach ; Function to count minimum number of jumps required to sort the array ; Stores minimum number of jumps ; Stores distances of jumps ; Stores the array elements with their starting indices ; Push the pairs { arr [ i ] , i + 1 } into the vector of pairs vect ; Update vect ; Populate the array temp [ ] ; Update temp [ arr [ i ] ] ; Sort the vector in the ascending order ; Jump till the previous index <= current index ; Update vect [ i ] ; Increment the number of jumps ; Print the minimum number of jumps required ; Driver Code ; Input ; Size of the array
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minJumps ( int arr [ ] , int jump [ ] , int N ) { int jumps = 0 ; int temp [ 1000 ] ; vector < pair < int , int > > vect ; for ( int i = 0 ; i < N ; i ++ ) { vect . push_back ( { arr [ i ] , i + 1 } ) ; } for ( int i = 0 ; i < N ; i ++ ) { temp [ arr [ i ] ] = jump [ i ] ; } sort ( vect . begin ( ) , vect . end ( ) ) ; for ( int i = 1 ; i < N ; i ++ ) { while ( vect [ i ] . second <= vect [ i - 1 ] . second ) { vect [ i ] = make_pair ( vect [ i ] . first , vect [ i ] . second + temp [ vect [ i ] . first ] ) ; jumps ++ ; } } cout << jumps << endl ; } int main ( ) { int arr [ ] = { 3 , 2 , 1 } ; int jump [ ] = { 1 , 1 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; minJumps ( arr , jump , N ) ; return 0 ; }