Minimum number of moves to make M and N equal by repeatedly adding any divisor of number to itself except 1 and the number | 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
def countOperations ( N , M ) : NEW_LINE INDENT visited = [ False ] * ( 100001 ) NEW_LINE Q = [ ] NEW_LINE Q . append ( [ N , 0 ] ) NEW_LINE visited [ N ] = True NEW_LINE while ( len ( Q ) > 0 ) : NEW_LINE INDENT aux = Q [ 0 ] [ 0 ] NEW_LINE cont = Q [ 0 ] [ 1 ] NEW_LINE Q . pop ( 0 ) NEW_LINE if ( aux == M ) : NEW_LINE INDENT return cont NEW_LINE DEDENT i = 2 NEW_LINE while i * i <= aux : NEW_LINE INDENT if ( aux % i == 0 ) : NEW_LINE INDENT if ( aux + i <= M and not visited [ aux + i ] ) : NEW_LINE INDENT Q . append ( [ aux + i , cont + 1 ] ) NEW_LINE visited [ aux + i ] = True NEW_LINE DEDENT if ( aux + int ( aux / i ) <= M and not visited [ aux + int ( aux / i ) ] ) : NEW_LINE INDENT Q . append ( [ aux + int ( aux / i ) , cont + 1 ] ) NEW_LINE visited [ aux + int ( aux / i ) ] = True NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT N , M = 4 , 24 NEW_LINE print ( countOperations ( N , M ) ) NEW_LINE