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
using System ; using System . Collections . Generic ; class GFG { static int isPresent ( int n , int x ) { string num = n . ToString ( ) ; for ( int i = 0 ; i < num . Length ; i ++ ) { if ( ( ( int ) num [ i ] - 97 ) == x ) return i ; } return - 1 ; } static int removeDigit ( int n , int index ) { string num = n . ToString ( ) ; string ans = " " ; for ( int i = 0 ; i < num . Length ; i ++ ) { if ( i != index ) ans += num [ i ] ; } if ( ans == " " || ( ans . Length == 1 && ans [ 0 ] == '0' ) ) return - 1 ; int x = Int32 . Parse ( ans ) ; ; return x ; } static bool reduceNtoX ( int a , int b , int [ ] d , int n ) { Queue < int > q = new Queue < int > ( ) ; q . Enqueue ( a ) ; Dictionary < int , bool > visited = new Dictionary < int , bool > ( ) ; visited [ a ] = true ; while ( q . Count > 0 ) { int top = q . Peek ( ) ; q . Dequeue ( ) ; 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 . ContainsKey ( top / d [ i ] ) && visited [ top / d [ i ] ] == false ) { q . Enqueue ( 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 . ContainsKey ( newElement ) && visited [ newElement ] == false ) ) { q . Enqueue ( newElement ) ; visited [ newElement ] = true ; } } } } return true ; } public static void Main ( ) { int A = 5643 , B = 81 ; int [ ] D = { 3 , 8 , 1 } ; int N = D . Length ; if ( reduceNtoX ( A , B , D , N ) ) Console . Write ( " Yes " ) ; else Console . Write ( " No " ) ; } }