Encuentre el entero positivo mínimo tal que sea divisible por A y la suma de sus dígitos sea igual a B

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)

Publicación traducida automáticamente

Artículo escrito por Samdare B y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *