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 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: