Convert a number to another by dividing by its factor or removing first occurrence of a digit from an array | Java 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
import java . util . * ; class GFG { static int isPresent ( int n , int x ) { String num = String . valueOf ( n ) ; for ( int i = 0 ; i < num . length ( ) ; i ++ ) { if ( ( num . charAt ( i ) - '0' ) == x ) return i ; } return - 1 ; } static int removeDigit ( int n , int index ) { String num = String . valueOf ( n ) ; String ans = " " ; for ( int i = 0 ; i < num . length ( ) ; i ++ ) { if ( i != index ) ans += num . charAt ( i ) ; } if ( ans == " " || ( ans . length ( ) == 1 && ans . charAt ( 0 ) == '0' ) ) return - 1 ; int x = Integer . valueOf ( ans ) ; return x ; } static boolean reduceNtoX ( int a , int b , int d [ ] , int n ) { Queue < Integer > q = new LinkedList < > ( ) ; q . add ( a ) ; Map < Integer , Boolean > visited = new HashMap < > ( ) ; visited . put ( a , true ) ; while ( ! q . isEmpty ( ) ) { int top = q . peek ( ) ; q . poll ( ) ; 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 . getOrDefault ( top / d [ i ] , false ) ) { q . add ( top / d [ i ] ) ; visited . put ( top / d [ i ] , true ) ; } int index = isPresent ( top , d [ i ] ) ; if ( index != - 1 ) { int newElement = removeDigit ( top , index ) ; if ( newElement != - 1 && ( ! visited . getOrDefault ( newElement , false ) ) ) { q . add ( newElement ) ; visited . put ( newElement , true ) ; } } } } return false ; } public static void main ( String [ ] args ) { int A = 5643 , B = 81 ; int D [ ] = { 3 , 8 , 1 } ; int N = D . length ; if ( reduceNtoX ( A , B , D , N ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }