Suppose two positive natural numbers A, B, and an array D[] consisting only of digits [0-9].
Convert a number to another by dividing its factors the main task is to check if it is possible to reduce A to B by repeatedly dividing by any of its factors which are present in the array D[] or by removing the first occurrence of any of its digit which is present in the array D[].
Example:
Input: A = 5643, B = 81, D[] = {3, 8, 1}
Output: Yes
Explanation:
Operation 1: Divide A (= 5643) by 3, then the value of A becomes 1881.
Operation 2: Remove the first occurrence of 8 from A(= 1881), then the value of A becomes 181.
Operation 3: Remove the first occurrence of 1 from A(= 181), then the value of A becomes 81.
Input: A = 82, B = 2, D[] = {8, 2}
Output: Yes
How to get this approach?
The given problem can be solved by performing all the possible operation on the value of A using the Queue and check by dividing the factors of an array D[] which return the integer value B.
So follow the steps below to solve the problem.
Step-1: Initialize a queue(Q) and then push A to it.
Step-2: Then initialize a Hashmap(M), store the elements present in Q and initialize a variable, ans as “No” store the required result.
Step-3: Iterate until Q is not empty and performing the following steps:
- Store the front of the Q in a variable, top.
- If the value of the top is equal to B, update the value of ans to “Yes” and break out of the loop.
- Otherwise, traverse the array, D[] and for each element, D[i] check the two conditions:
- If D[i] is a factor of top, then push the value quotient obtained on dividing top by D[i] in the queue Q and mark it as visited in M.
- If D[i] is present in the number top, then remove its first occurrence and push the new number obtained in queue Q and mark it as visited in M.
Step-4: After completing the above steps, print the value of ans as the result.
Finally implementation of above approach:
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a digit x is // present in the number N or not int isPresent(int n, int x) { // Convert N to string string num = to_string(n); // Traverse the string num for (int i = 0; i < num.size(); i++) { // Return first occurrence // of the digit x if ((num[i] - '0') == x) return i; } return -1; } // Function to remove the character // at a given index from the number int removeDigit(int n, int index) { // Convert N to string string num = to_string(n); // Store the resultant string string ans = ""; // Traverse the string num for (int i = 0; i < num.size(); i++) { if (i != index) ans += num[i]; } // If the number becomes empty // after deletion, then return -1 if (ans == "" || (ans.size() == 1 && ans[0] == '0')) return -1; // Return the number int x = stoi(ans); return x; } // Function to check if A can be // reduced to B by performing the // operations any number of times bool reduceNtoX(int a, int b, int d[], int n) { // Create a queue queue<int> q; // Push A into the queue q.push(a); // Hashmap to check if the element // is present in the Queue or not unordered_map<int, bool> visited; // Set A as visited visited[a] = true; // Iterate while the queue is not empty while (!q.empty()) { // Store the front value of the // queue and pop it from it int top = q.front(); q.pop(); if (top < 0) continue; // If top is equal to B, // then return true if (top == b) return true; // Traverse the array, D[] for (int i = 0; i < n; i++) { // Divide top by D[i] if // it is possible and // push the result in q if (d[i] != 0 && top % d[i] == 0 && !visited[top / d[i]]) { q.push(top / d[i]); visited[top / d[i]] = true; } // If D[i] is present at the top int index = isPresent(top, d[i]); if (index != -1) { // Remove the first occurrence // of D[i] from the top and // store the new number int newElement = removeDigit(top, index); // Push newElement into the queue q if (newElement != -1 && (!visited[newElement])) { q.push(newElement); visited[newElement] = true; } } } } // Return false if A can // not be reduced to B return false; } // Driver Code 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; }
Output:
Yes
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Please comment and share this article, and if you find anything is incorrect then WhatsApp me.