Minimum number of sum and modulo operations using given numbers to reach target | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minPushes ( int N , int K , vector < int > arr ) { vector < int > dp ( 100000 , -1 ) ; dp [ N ] = 0 ; for ( int i = 0 ; i < arr . size ( ) ; 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 ] ; } int main ( ) { int N = 99880 , K = 89 ; vector < int > arr { 100 , 3 } ; cout << minPushes ( N , K , arr ) ; return 0 ; }