# Write A Program convert a number to another by dividing its factor or removing the first occurrence of a digit from an array

Suppose two positive natural numbers AB, 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'))
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);

if (reduceNtoX(A, B, D, N))
cout << "Yes";
else
cout << "No";

return 0;
}```

Output:

``Yes``

Time Complexity: O(2N)
Auxiliary Space: O(2N)