Minimum number of sum and modulo operations using given numbers to reach target | Java implementation of the above approach ; Function to find the minimum moves to reach K from N ; Initialization of dp vector ; dp [ i ] = minimum pushes required to reach i ; Traversing through the buttons ; Iterating through all the positions ; If not visited ; Next status of lock ; Advance to next state ; Return the final dp [ target ] ; Driver function ; Given Input ; Function Call
class GFG { static int minPushes ( int N , int K , int [ ] arr ) { int [ ] dp = new int [ 100000 ] ; for ( int i = 0 ; i < dp . length ; i ++ ) dp [ i ] = - 1 ; dp [ N ] = 0 ; for ( int i = 0 ; i < arr . length ; i ++ ) { for ( int xx = 0 ; xx < 100000 ; xx ++ ) { int x = xx ; if ( dp [ x ] == - 1 ) continue ; int next = ( x + arr [ i ] ) % 100000 ; while ( dp [ next ] == - 1 dp [ next ] > dp [ x ] + 1 ) { dp [ next ] = dp [ x ] + 1 ; x = next ; next = ( next + arr [ i ] ) % 100000 ; } } } return dp [ K ] ; } public static void main ( String [ ] args ) { int N = 99880 , K = 89 ; int [ ] arr = { 100 , 3 } ; System . out . print ( minPushes ( N , K , arr ) ) ; } }