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
using System ; using System . Collections . Generic ; class GFG { static void minJumps ( int [ ] w , int [ ] l , int n ) { if ( n == 1 ) { Console . Write ( 0 ) ; return ; } int ans = 0 ; Dictionary < int , int > pos = new Dictionary < int , int > ( ) ; Dictionary < int , int > jump = new Dictionary < int , int > ( ) ; Dictionary < int , bool > filled = new Dictionary < int , bool > ( ) ; int [ ] a = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { if ( pos . ContainsKey ( w [ i ] ) ) pos [ w [ i ] ] = i ; else pos . Add ( w [ i ] , i ) ; if ( filled . ContainsKey ( w [ i ] ) ) filled [ i ] = true ; else filled . Add ( i , true ) ; if ( jump . ContainsKey ( w [ i ] ) ) jump [ w [ i ] ] = l [ i ] ; else jump . Add ( w [ i ] , l [ i ] ) ; a [ i ] = w [ i ] ; } Array . Sort ( a ) ; 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 . ContainsKey ( currElementPos ) && filled [ currElementPos ] ) { currElementPos += jump [ a [ curr ] ] ; ans ++ ; } if ( pos . ContainsKey ( a [ curr ] ) ) pos [ a [ curr ] ] = currElementPos ; else pos . Add ( a [ curr ] , currElementPos ) ; if ( filled . ContainsKey ( currElementPos ) ) filled [ currElementPos ] = true ; else filled . Add ( currElementPos , true ) ; } Console . Write ( ans ) ; } public static void Main ( ) { int [ ] W = { 2 , 1 , 4 , 3 } ; int [ ] L = { 4 , 1 , 2 , 4 } ; int N = W . Length ; minJumps ( W , L , N ) ; } }