Dados dos números enteros A y B , la tarea es encontrar el número entero positivo mínimo N tal que N sea divisible por A y la suma de los dígitos de N sea igual a B. Si no se encuentra el número, imprima -1 .
Ejemplos:
Entrada: A = 20, B = 30
Salida: 49980
49980 es divisible por 20 y suma de su dígito = 4 + 9 + 9 + 8 + 0 = 30
Entrada: A = 5, B = 2
Salida: 20
Acercarse:
- Cree una cola vacía q que almacene el valor de A y B y el número de salida como una string y cree una array bidimensional de tipo entero visitada[][] que almacene el dígito visitado.
- Inserte el Node en la cola y verifique si la cola no está vacía.
- Si bien la cola no está vacía, extraiga un elemento de la cola y, para cada dígito del 1 al 9 , concatene el dígito después de la string num y verifique si el número formado es el número requerido.
- Si se encuentra el número requerido, imprima el número.
- De lo contrario, repita los pasos mientras el número es menor que B y la cola no está vacía mientras empuja el número no visitado a la cola.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Array that stores visited digits
int visited[501][5001];
// Structure for queue Node.
struct Node {
int a, b;
string str;
};
// Function to return the minimum number such that it is
// divisible by 'a' and sum of its digits is equals to 'b'
int findNumber(int a, int b)
{
// Create queue
queue<Node> q;
// Initially queue is empty
Node temp = Node{ 0, 0, "" };
// Initialize visited to 1
visited[0][0] = 1;
// Push temp in queue
q.push(temp);
// While queue is not empty
while (!q.empty()) {
// Get the front of the queue and pop it
Node u = q.front();
q.pop();
// If popped element is the required number
if (u.a == 0 && u.b == b)
// Parse int from string and return it
return std::stoi(u.str);
// Loop for each digit and check the sum
// If not visited then push it to the queue
for (int i = 0; i < 10; i++) {
int dd = (u.a * 10 + i) % a;
int ss = u.b + i;
if (ss <= b && !visited[dd][ss]) {
visited[dd][ss] = 1;
q.push(Node{ dd, ss, u.str + char('0' + i) });
}
}
}
// Required number not found return -1.
return -1;
}
// Driver code.
int main()
{
int a = 25, b = 1;
cout << findNumber(a, b);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class Solution
{
// Array that stores visited digits
static int visited[][]= new int[501][5001];
// Structure for queue Node.
static class Node {
int a, b;
String str;
Node(int a1,int b1,String s)
{
a=a1;
b=b1;
str=s;
}
}
// Function to return the minimum number such that it is
// divisible by 'a' and sum of its digits is equals to 'b'
static int findNumber(int a, int b)
{
// Create queue
Queue<Node> q= new LinkedList<Node>();
// Initially queue is empty
Node temp =new Node( 0, 0, "" );
// Initialize visited to 1
visited[0][0] = 1;
// Push temp in queue
q.add(temp);
// While queue is not empty
while (q.size()!=0) {
// Get the front of the queue and pop it
Node u = q.peek();
q.remove();
// If popped element is the required number
if (u.a == 0 && u.b == b)
// Parse int from string and return it
return Integer.parseInt(u.str);
// Loop for each digit and check the sum
// If not visited then push it to the queue
for (int i = 0; i < 10; i++) {
int dd = (u.a * 10 + i) % a;
int ss = u.b + i;
if (ss <= b && visited[dd][ss]==0) {
visited[dd][ss] = 1;
q.add(new Node( dd, ss, u.str + (char)('0' + i) ));
}
}
}
// Required number not found return -1.
return -1;
}
// Driver code.
public static void main(String args[])
{
//initialize visited
for(int i=0;i<500;i++)
for(int j=0;j<500;j++)
visited[i][j]=0;
int a = 25, b = 1;
System.out.println(findNumber(a, b));
}
}
//contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Array that stores visited digits visited = [[0 for x in range(501)] for y in range(5001)] # Structure for queue Node. class Node: def __init__(self, a, b, string): self.a = a self.b = b self.string = string # Function to return the minimum number # such that it is divisible by 'a' and # sum of its digits is equals to 'b' def findNumber(a, b): # Use list as queue q = [] # Initially queue is empty temp = Node(0, 0, "") # Initialize visited to 1 visited[0][0] = 1 # Push temp in queue q.append(temp) # While queue is not empty while len(q) > 0: # Get the front of the queue # and pop it u = q.pop(0) # If popped element is the # required number if u.a == 0 and u.b == b: # Parse int from string # and return it return int(u.string) # Loop for each digit and check the sum # If not visited then push it to the queue for i in range(0, 10): dd = (u.a * 10 + i) % a ss = u.b + i if ss <= b and visited[dd][ss] == False: visited[dd][ss] = 1 q.append(Node(dd, ss, u.string + str(i))) # Required number not found return -1. return -1 # Driver code. if __name__ == "__main__": a, b = 25, 1 print(findNumber(a, b)) # This code is contributed by Rituraj Jain
Javascript
<script>
// Javascript implementation of the approach
// Array that stores visited digits
let visited=new Array(501);
for(let i = 0; i < 501; i++)
{
visited[i] = new Array(5001);
for(let j = 0; j < 5001; j++)
visited[i][j] = 0;
}
// Structure for queue Node.
class Node
{
constructor(a1, b1, s)
{
this.a = a1;
this.b = b1;
this.str = s;
}
}
// Function to return the minimum number such that it is
// divisible by 'a' and sum of its digits is equals to 'b'
function findNumber(a,b)
{
// Create queue
let q= [];
// Initially queue is empty
let temp = new Node( 0, 0, "" );
// Initialize visited to 1
visited[0][0] = 1;
// Push temp in queue
q.push(temp);
// While queue is not empty
while (q.length != 0) {
// Get the front of the queue and pop it
let u = q[0];
q.shift();
// If popped element is the required number
if (u.a == 0 && u.b == b)
// Parse int from string and return it
return parseInt(u.str);
// Loop for each digit and check the sum
// If not visited then push it to the queue
for (let i = 0; i < 10; i++) {
let dd = (u.a * 10 + i) % a;
let ss = u.b + i;
if (ss <= b && visited[dd][ss] == 0) {
visited[dd][ss] = 1;
q.push(new Node( dd, ss, u.str + String.fromCharCode('0'.charCodeAt(0) + i) ));
}
}
}
// Required number not found return -1.
return -1;
}
// Driver code.
let a = 25, b = 1;
document.write(findNumber(a, b));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
100
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)