Convert a number to another by dividing by its factor or removing first occurrence of a digit from an array | Python3 program for the above approach ; Function to check if a digit x is present in the number N or not ; Convert N to string ; Traverse the num ; Return first occurrence of the digit x ; Function to remove the character at a given index from the number ; Convert N to string ; Store the resultant string ; Traverse the num ; If the number becomes empty after deletion , then return - 1 ; Return the number ; Function to check if A can be reduced to B by performing the operations any number of times ; Create a queue ; Push A into the queue ; Hashmap to check if the element is present in the Queue or not ; Set A as visited ; Iterate while the queue is not empty ; Store the front value of the queue and pop it from it ; If top is equal to B , then return true ; Traverse the array , D [ ] ; Divide top by D [ i ] if it is possible and push the result in q ; If D [ i ] is present at the top ; Remove the first occurrence of D [ i ] from the top and store the new number ; Push newElement into the queue q ; Return false if A can not be reduced to B ; Driver Code
from collections import deque NEW_LINE def isPresent ( n , x ) : NEW_LINE INDENT num = str ( n ) NEW_LINE for i in range ( len ( num ) ) : NEW_LINE INDENT if ( ( ord ( num [ i ] ) - ord ( '0' ) ) == x ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT def removeDigit ( n , index ) : NEW_LINE INDENT num = str ( n ) NEW_LINE ans = " " NEW_LINE for i in range ( len ( num ) ) : NEW_LINE INDENT if ( i != index ) : NEW_LINE INDENT ans += num [ i ] NEW_LINE DEDENT DEDENT if ( ans == " " or ( len ( ans ) == 1 and ans [ 0 ] == '0' ) ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT x = int ( ans ) NEW_LINE return x NEW_LINE DEDENT def reduceNtoX ( a , b , d , n ) : NEW_LINE INDENT q = deque ( ) NEW_LINE q . append ( a ) NEW_LINE visited = { } NEW_LINE visited [ a ] = True NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT top = q . popleft ( ) NEW_LINE if ( top < 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( top == b ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( d [ i ] != 0 and top % d [ i ] == 0 and ( top // d [ i ] not in visited ) ) : NEW_LINE INDENT q . append ( top // d [ i ] ) NEW_LINE visited [ top // d [ i ] ] = True NEW_LINE DEDENT index = isPresent ( top , d [ i ] ) NEW_LINE if ( index != - 1 ) : NEW_LINE INDENT newElement = removeDigit ( top , index ) NEW_LINE if ( newElement != - 1 and ( newElement not in visited ) ) : NEW_LINE INDENT q . append ( newElement ) NEW_LINE visited [ newElement ] = True NEW_LINE DEDENT DEDENT DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A , B = 5643 , 81 NEW_LINE D = [ 3 , 8 , 1 ] NEW_LINE N = len ( D ) NEW_LINE if ( reduceNtoX ( A , B , D , N ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT