Minimum number of jumps required to sort numbers placed on a number line | C ++ program for the above approach ; Function to find the minimum number of jumps required to sort the array ; Base Case ; Store the required result ; Stores the current position of elements and their respective maximum jump ; Used to check if a position is already taken by another element ; Stores the sorted array a [ ] ; Traverse the array w [ ] & update positions jumps array a [ ] ; Sort the array a [ ] ; Traverse the array a [ ] over the range [ 1 , N - 1 ] ; Store the index of current element and its just smaller element in array w [ ] ; Iterate until current element position is at most its just smaller element position ; Update the position of the current element ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minJumps ( int w [ ] , int l [ ] , int n ) { if ( n == 1 ) { cout << 0 ; return ; } int ans = 0 ; unordered_map < int , int > pos , jump ; unordered_map < int , bool > filled ; int a [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { pos [ w [ i ] ] = i ; filled [ i ] = true ; jump [ w [ i ] ] = l [ i ] ; a [ i ] = w [ i ] ; } sort ( a , a + n ) ; for ( int curr = 1 ; curr < n ; curr ++ ) { int currElementPos = pos [ a [ curr ] ] ; int prevElementPos = pos [ a [ curr - 1 ] ] ; if ( currElementPos > prevElementPos ) continue ; while ( currElementPos <= prevElementPos filled [ currElementPos ] ) { currElementPos += jump [ a [ curr ] ] ; ans ++ ; } pos [ a [ curr ] ] = currElementPos ; filled [ currElementPos ] = true ; } cout << ans ; } int main ( ) { int W [ ] = { 2 , 1 , 4 , 3 } ; int L [ ] = { 4 , 1 , 2 , 4 } ; int N = sizeof ( W ) / sizeof ( W [ 0 ] ) ; minJumps ( W , L , N ) ; return 0 ; }