Dados dos enteros positivos A , B , y una array D[] que consta solo de dígitos [0-9] , la tarea es verificar si es posible reducir A a B dividiendo repetidamente por cualquiera de sus factores que está presente el array D[] o eliminando la primera aparición de cualquiera de sus dígitos que esté presente en la array D[] .
Ejemplos:
Entrada: A = 5643, B = 81, D[] = {3, 8, 1}
Salida: Sí
Explicación:
Operación 1: Divide A (= 5643) entre 3, luego el valor de A se convierte en 1881.
Operación 2: Elimina la primera ocurrencia de 8 de A(= 1881), entonces el valor de A se convierte en 181.
Operación 3: Elimina la primera ocurrencia de 1 de A(= 181), luego el valor de A se convierte en 81.Entrada: A = 82, B = 2, D[] = {8, 2}
Salida: Sí
Enfoque: El problema dado se puede resolver realizando todas las operaciones posibles sobre el valor A usando la Cola y verificando si en algún paso el valor de A se modifica a B o no. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola , diga Q e inicialmente empuje A hacia ella.
- Inicialice un HashMap , diga M para almacenar los elementos presentes en la cola Q e inicialice una variable, responda como «No» para almacenar el resultado requerido.
- Iterar hasta que Q no esté vacío y realizar los siguientes pasos:
- Guarde el frente de la Q en una variable, top .
- Si el valor de la parte superior es igual a B , actualice el valor de ans a «Sí» y salga del bucle .
- De lo contrario, recorra la array , D[] y para cada elemento, D[i] verifique las dos condiciones:
- Si D[i] es un factor de top , entonces empuje el valor del cociente obtenido al dividir top por D[i] en la cola Q y márquelo como visitado en M .
- Si D[i] está presente en el número superior , elimine su primera aparición y empuje el nuevo número obtenido en la cola Q y márquelo como visitado en M.
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check if a digit x is
// present in the number N or not
static int isPresent(int n, int x)
{
// Convert N to string
String num = String.valueOf(n);
// Traverse the string num
for (int i = 0; i < num.length();
i++) {
// Return first occurrence
// of the digit x
if ((num.charAt(i) - '0') == x)
return i;
}
return -1;
}
// Function to remove the character
// at a given index from the number
static int removeDigit(int n, int index)
{
// Convert N to string
String num = String.valueOf(n);
// Store the resultant string
String ans = "";
// Traverse the string num
for (int i = 0;
i < num.length(); i++)
{
if (i != index)
ans += num.charAt(i);
}
// If the number becomes empty
// after deletion, then return -1
if (ans == "" || (ans.length() == 1
&& ans.charAt(0) == '0'))
return -1;
// Return the number
int x = Integer.valueOf(ans);
return x;
}
// Function to check if A can be
// reduced to B by performing the
// operations any number of times
static boolean reduceNtoX(int a, int b,
int d[], int n)
{
// Create a queue
Queue<Integer> q=new LinkedList<>();
// Push A into the queue
q.add(a);
// Hashmap to check if the element
// is present in the Queue or not
Map<Integer, Boolean> visited= new HashMap<>();
// Set A as visited
visited.put(a,true);
// Iterate while the queue is not empty
while (!q.isEmpty()) {
// Store the front value of the
// queue and pop it from it
int top = q.peek();
q.poll();
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.getOrDefault(top / d[i], false)) {
q.add(top / d[i]);
visited.put(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.getOrDefault(newElement,false))) {
q.add(newElement);
visited.put(newElement, true);
}
}
}
}
// Return false if A can
// not be reduced to B
return false;
}
// Driver code
public static void main (String[] args)
{
// Given inputs
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");
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
from collections import deque
# Function to check if a digit x is
# present in the number N or not
def isPresent(n, x):
# Convert N to string
num = str(n)
# Traverse the num
for i in range(len(num)):
# Return first occurrence
# of the digit x
if ((ord(num[i]) - ord('0')) == x):
return i
return -1
# Function to remove the character
# at a given index from the number
def removeDigit(n, index):
# Convert N to string
num = str(n)
# Store the resultant string
ans = ""
# Traverse the num
for i in range(len(num)):
if (i != index):
ans += num[i]
# If the number becomes empty
# after deletion, then return -1
if (ans == "" or (len(ans) == 1 and
ans[0] == '0')):
return -1
# Return the number
x = int(ans)
return x
# Function to check if A can be
# reduced to B by performing the
# operations any number of times
def reduceNtoX(a, b, d, n):
# Create a queue
q = deque()
# Push A into the queue
q.append(a)
# Hashmap to check if the element
# is present in the Queue or not
visited = {}
# Set A as visited
visited[a] = True
# Iterate while the queue is not empty
while (len(q) > 0):
# Store the front value of the
# queue and pop it from it
top = q.popleft()
if (top < 0):
continue
# If top is equal to B,
# then return true
if (top == b):
return True
# Traverse the array, D[]
for i in range(n):
# Divide top by D[i] if
# it is possible and
# push the result in q
if (d[i] != 0 and top % d[i] == 0 and
(top // d[i] not in visited)):
q.append(top // d[i])
visited[top // d[i]] = True
# If D[i] is present at the top
index = isPresent(top, d[i])
if (index != -1):
# Remove the first occurrence
# of D[i] from the top and
# store the new number
newElement = removeDigit(top, index)
# Push newElement into the queue q
if (newElement != -1 and
(newElement not in visited)):
q.append(newElement)
visited[newElement] = True
# Return false if A can
# not be reduced to B
return False
# Driver Code
if __name__ == '__main__':
A, B = 5643, 81
D = [ 3, 8, 1 ]
N = len(D)
if (reduceNtoX(A, B, D, N)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if a digit x is
// present in the number N or not
static int isPresent(int n, int x)
{
// Convert N to string
string num = n.ToString();
// Traverse the string num
for (int i = 0; i < num.Length;
i++) {
// Return first occurrence
// of the digit x
if (((int)num[i] - 97) == x)
return i;
}
return -1;
}
// Function to remove the character
// at a given index from the number
static int removeDigit(int n, int index)
{
// Convert N to string
string num = n.ToString();
// Store the resultant string
string ans = "";
// Traverse the string num
for (int i = 0;
i < num.Length; i++) {
if (i != index)
ans += num[i];
}
// If the number becomes empty
// after deletion, then return -1
if (ans == "" || (ans.Length == 1
&& ans[0] == '0'))
return -1;
// Return the number
int x = Int32.Parse(ans);;
return x;
}
// Function to check if A can be
// reduced to B by performing the
// operations any number of times
static bool reduceNtoX(int a, int b,
int []d, int n)
{
// Create a queue
Queue<int> q = new Queue<int>();
// Push A into the queue
q.Enqueue(a);
// Hashmap to check if the element
// is present in the Queue or not
Dictionary<int,bool> visited = new Dictionary<int,bool>();
// Set A as visited
visited[a] = true;
// Iterate while the queue is not empty
while (q.Count>0) {
// Store the front value of the
// queue and pop it from it
int top = q.Peek();
q.Dequeue();
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.ContainsKey(top / d[i]) && visited[top / d[i]]==false) {
q.Enqueue(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.ContainsKey(newElement) && visited[newElement]==false)) {
q.Enqueue(newElement);
visited[newElement] = true;
}
}
}
}
// Return false if A can
// not be reduced to B
return true;
}
// Driver Code
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");
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to check if a digit x is
// present in the number N or not
function isPresent(n,x)
{
// Convert N to string
let num = (n).toString();
// Traverse the string num
for (let i = 0; i < num.length;
i++) {
// Return first occurrence
// of the digit x
if ((num[i].charCodeAt(0) - '0'.charCodeAt(0)) == x)
return i;
}
return -1;
}
// Function to remove the character
// at a given index from the number
function removeDigit(n,index)
{
// Convert N to string
let num = (n).toString();
// Store the resultant string
let ans = "";
// Traverse the string num
for (let i = 0;
i < num.length; i++)
{
if (i != index)
ans += num[i];
}
// If the number becomes empty
// after deletion, then return -1
if (ans == "" || (ans.length == 1
&& ans[0] == '0'))
return -1;
// Return the number
let x = parseInt(ans);
return x;
}
// Function to check if A can be
// reduced to B by performing the
// operations any number of times
function reduceNtoX(a,b,d,n)
{
// Create a queue
let q=[];
// Push A into the queue
q.push(a);
// Hashmap to check if the element
// is present in the Queue or not
let visited= new Map();
// Set A as visited
visited.set(a,true);
// Iterate while the queue is not empty
while (q.length!=0) {
// Store the front value of the
// queue and pop it from it
let top = q.shift();
if (top < 0)
continue;
// If top is equal to B,
// then return true
if (top == b)
return true;
// Traverse the array, D[]
for (let i = 0; i < n; i++) {
// Divide top by D[i] if
// it is possible and
// push the result in q
if(!visited.has(top / d[i]))
visited.set(top / d[i],false);
if (d[i] != 0 && top % d[i] == 0
&& !visited.get(top / d[i])) {
q.push(top / d[i]);
visited.set(top / d[i], true);
}
// If D[i] is present at the top
let index = isPresent(top, d[i]);
if (index != -1) {
// Remove the first occurrence
// of D[i] from the top and
// store the new number
let newElement
= removeDigit(top, index);
if(!visited.has(newElement))
visited.set(newElement,false);
// Push newElement into the queue q
if (newElement != -1
&& (!visited.get(newElement))) {
q.push(newElement);
visited.set(newElement, true);
}
}
}
}
// Return false if A can
// not be reduced to B
return false;
}
// Driver code
// Given inputs
let A = 5643, B = 81;
let D = [ 3, 8, 1 ];
let N = D.length;
if (reduceNtoX(A, B, D, N))
document.write("Yes");
else
document.write("No");
// This code is contributed by unknown2108
</script>
Producción:
Yes
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(2 N )
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA