Encuentra el múltiplo de dígito binario más pequeño de un número dado

Un número decimal se llama número de dígito binario si sus dígitos son binarios. Por ejemplo, 102 no es un número de dígito binario y 101 sí lo es.
Nos dan un número decimal N, necesitamos encontrar el múltiplo más pequeño de N que es un número de dígito binario, 

Ejemplos:  

Input : N = 2
Output: 10
Explanation: 10 is a multiple of 2. 
              Note that 5 * 2 = 10

Input  : N = 17
Output : 11101
Explanation: 11101 is a multiple of 17. 
              Note that 653 * 17 = 11101

Podemos resolver este problema usando BFS , cada Node del gráfico implícito será un número de dígito binario y si el número es x, entonces su siguiente Node de nivel será x0 y x1 (x concatenado con 0 y 1). 
Al comenzar, empujaremos 1 a nuestra cola, lo que empujará 10 y 11 a la cola más tarde y así sucesivamente, después de tomar el número de la cola, verificaremos si este número es múltiplo de un número dado o no, si es así, entonces devuelva este número como resultado, este será nuestro resultado final porque BFS avanza nivel por nivel, por lo que la primera respuesta que obtengamos también será nuestra respuesta más pequeña. 
En el siguiente código, el número de dígitos binarios se trata como una string, porque para algunos números puede ser muy grande y puede estar fuera del límite incluso de una operación larga, mod en el número almacenado como string también se implementa. 

El principal ajuste de optimización del código es usar un conjunto para el valor modular, si anteriormente se produjo una string con el mismo valor de mod, no insertaremos esta nueva string en nuestra cola. La razón por la que no se presiona una nueva string se explica a continuación, 

Sean x e y strings, lo que da el mismo valor modular. Sea x el menor. sea ​​z otra string que cuando se agrega a y nos da un número divisible por N. Si es así, también podemos agregar esta string a x, que es más pequeña que y, y aun así obtener un número divisible por n. Entonces podemos ignorar y con seguridad, ya que el resultado más pequeño se obtendrá solo a través de x.

Implementación:

// C++ code to get the smallest multiple of N with
// binary digits only.
#include <bits/stdc++.h>
using namespace std;
 
// Method return t % N, where t is stored as
// a string
int mod(string t, int N)
{
    int r = 0;
    for (int i = 0; i < t.length(); i++)
    {
        r = r * 10 + (t[i] - '0');
        r %= N;
    }
    return r;
}
 
// method returns smallest multiple which has
// binary digits
string getMinimumMultipleOfBinaryDigit(int N)
{
    queue<string> q;
    set<int> visit;
 
    string t = "1";
 
    //  In starting push 1 into our queue
    q.push(t);
 
    //  loop until queue is not empty
    while (!q.empty())
    {
        // Take the front number from queue.
        t = q.front();      q.pop();
 
        // Find remainder of t with respect to N.
        int rem = mod(t, N);
 
        // if remainder is 0 then we have
        // found our solution
        if (rem == 0)
            return t;
 
        // If this remainder is not previously seen,
        // then push t0 and t1 in our queue
        else if(visit.find(rem) == visit.end())
        {
            visit.insert(rem);
            q.push(t + "0");
            q.push(t + "1");
        }
    }
}
 
//  Driver code to test above methods
int main()
{
    int N = 12;
    cout << getMinimumMultipleOfBinaryDigit(N);
    return 0;
}

// Java code to get the smallest multiple
// of N with binary digits only.
import java.util.*;
import java.io.*;
 
class GFG{
 
// Method return t % N, where t is stored as
// a string
public static int mod(String t, int N)
{
    int r = 0;
    for(int i = 0; i < t.length(); i++)
    {
        r = r * 10 + (t.charAt(i) - '0');
        r %= N;
    }
    return r;
}
 
// method returns smallest multiple which has
// binary digits
public static String getMinimumMultipleOfBinaryDigit(int N)
{
    Queue<String> q = new LinkedList<String>();
    Set<Integer> visit = new HashSet<>();
 
    String t = "1";
 
    // In starting push 1 into our queue
    q.add(t);
 
    // loop until queue is not empty
    while (!q.isEmpty())
    {
         
        // Take the front number from queue.
        t = q.remove();
 
        // Find remainder of t with respect to N.
        int rem = mod(t, N);
         
        // If remainder is 0 then we have
        // found our solution
        if (rem == 0)
            return t;
 
        // If this remainder is not previously seen,
        // then push t0 and t1 in our queue
        else if(!visit.contains(rem))
        {
            visit.add(rem);
            q.add(t + "0");
            q.add(t + "1");
        }
    }
    return "";
}
 
// Driver code
public static void main (String[] args)
{
    int N = 12;
    System.out.println(
        getMinimumMultipleOfBinaryDigit(N));
}
}
 
// This code is contributed by
// Naresh Saharan and Sagar Jangra

def getMinimumMultipleOfBinaryDigit(A):
     
    # queue for BFS
    q = []
     
    # set of visited remainders
    visitedRem = set([])
    t = '1'
    q.append(t)
    while q:
        t = q.pop(0)
        rem = int(t) % A
        if rem == 0:
            return t
        if rem not in visitedRem:
            visitedRem.add(rem)
            q.append(t+'0')
            q.append(t+'1')
         
 
# Driver code
n = 12
print( getMinimumMultipleOfBinaryDigit(n))
 
# This code is contributed
# by Jeet9

// C# code to get the smallest
// multiple of N with binary
// digits only.
using System;
using System.Collections.Generic;
class GFG{
 
// Method return t % N,
// where t is stored as
// a string
public static int mod(String t,
                      int N)
{
  int r = 0;
  for(int i = 0;
          i < t.Length; i++)
  {
    r = r * 10 + (t[i] - '0');
    r %= N;
  }
  return r;
}
 
// method returns smallest
// multiple which has
// binary digits
public static String getMinimumMultipleOfBinaryDigit(int N)
{
  Queue<String> q = new Queue<String>();
  HashSet<int> visit = new HashSet<int>();
 
  String t = "1";
 
  // In starting push 1
  // into our queue
  q.Enqueue(t);
 
  // loop until queue
  // is not empty
  while (q.Count != 0)
  {
    // Take the front number
    // from queue.
    t = q.Dequeue();
 
    // Find remainder of t
    // with respect to N.
    int rem = mod(t, N);
 
    // If remainder is 0 then
    // we have found our solution
    if (rem == 0)
      return t;
 
    // If this remainder is not
    // previously seen, then push
    // t0 and t1 in our queue
    else if(!visit.Contains(rem))
    {
      visit.Add(rem);
      q.Enqueue(t + "0");
      q.Enqueue(t + "1");
    }
  }
  return "";
}
 
// Driver code
public static void Main(String[] args)
{
  int N = 12;
  Console.WriteLine(getMinimumMultipleOfBinaryDigit(N));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript code to get the smallest multiple of N with
// binary digits only.
 
// Method return t % N, where t is stored as
// a string
function mod(t,N)
{
    let r = 0;
    for (let i = 0; i < t.length; i++)
    {
        r = r * 10 + (t[i] - '0');
        r %= N;
    }
    return r;
}
 
// method returns smallest multiple which has
// binary digits
 
function getMinimumMultipleOfBinaryDigit(N)
{
    let q = [];
    let visit = new Set();
 
    let t = "1";
 
    // In starting push 1 into our queue
    q.push(t);
 
    // loop until queue is not empty
    while (q.length)
    {
        // Take the front number from queue.
        t = q[0];    
        q.shift();
 
        // Find remainder of t with respect to N.
        let rem = mod(t, N);
 
        // if remainder is 0 then we have
        // found our solution
        if (rem == 0)
            return t;
 
        // If this remainder is not previously seen,
        // then push t0 and t1 in our queue
        else if(visit.has(rem) == false)
        {
            visit.add(rem);
            q.push(t + "0");
            q.push(t + "1");
        }
    }
}
 
// Driver code to test above methods
 
let N = 12;
document.write(getMinimumMultipleOfBinaryDigit(N));
 
// This code is contributed by shinjanpatra.
</script>

11100

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.