Convert a number to another by dividing by its factor or removing first occurrence of a digit from an array | C ++ 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 string 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 string 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int isPresent ( int n , int x ) { string num = to_string ( n ) ; for ( int i = 0 ; i < num . size ( ) ; i ++ ) { if ( ( num [ i ] - '0' ) == x ) return i ; } return -1 ; } int removeDigit ( int n , int index ) { string num = to_string ( n ) ; string ans = " " ; for ( int i = 0 ; i < num . size ( ) ; i ++ ) { if ( i != index ) ans += num [ i ] ; } if ( ans == " " || ( ans . size ( ) == 1 && ans [ 0 ] == '0' ) ) return -1 ; int x = stoi ( ans ) ; return x ; } bool reduceNtoX ( int a , int b , int d [ ] , int n ) { queue < int > q ; q . push ( a ) ; unordered_map < int , bool > visited ; visited [ a ] = true ; while ( ! q . empty ( ) ) { int top = q . front ( ) ; q . pop ( ) ; if ( top < 0 ) continue ; if ( top == b ) return true ; for ( int i = 0 ; i < n ; i ++ ) { if ( d [ i ] != 0 && top % d [ i ] == 0 && ! visited [ top / d [ i ] ] ) { q . push ( top / d [ i ] ) ; visited [ top / d [ i ] ] = true ; } int index = isPresent ( top , d [ i ] ) ; if ( index != -1 ) { int newElement = removeDigit ( top , index ) ; if ( newElement != -1 && ( ! visited [ newElement ] ) ) { q . push ( newElement ) ; visited [ newElement ] = true ; } } } } return false ; } int main ( ) { int A = 5643 , B = 81 ; int D [ ] = { 3 , 8 , 1 } ; int N = sizeof ( D ) / sizeof ( D [ 0 ] ) ; if ( reduceNtoX ( A , B , D , N ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }