Minimum number of moves to make M and N equal by repeatedly adding any divisor of number to itself except 1 and the number | C ++ program for the above approach . ; Function to find the minimum number of moves to make N and M equal . ; Array to maintain the numbers included . ; pair of vertex , count ; run bfs from N ; if we reached goal ; Iterate in the range ; If i is a factor of aux ; If i is less than M - aux and is not included earlier . ; If aux / i is less than M - aux and is not included earlier . ; Not possible ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countOperations ( int N , int M ) { bool visited [ 100001 ] ; fill ( visited , visited + 100001 , false ) ; queue < pair < int , int > > Q ; Q . push ( make_pair ( N , 0 ) ) ; visited [ N ] = true ; while ( ! Q . empty ( ) ) { int aux = Q . front ( ) . first ; int cont = Q . front ( ) . second ; Q . pop ( ) ; if ( aux == M ) return cont ; for ( int i = 2 ; i * i <= aux ; i ++ ) if ( aux % i == 0 ) { if ( aux + i <= M && ! visited [ aux + i ] ) { Q . push ( make_pair ( aux + i , cont + 1 ) ) ; visited [ aux + i ] = true ; } if ( aux + aux / i <= M && ! visited [ aux + aux / i ] ) { Q . push ( make_pair ( aux + aux / i , cont + 1 ) ) ; visited [ aux + aux / i ] = true ; } } } return -1 ; } int main ( ) { int N = 4 , M = 24 ; cout << countOperations ( N , M ) ; return 0 ; }