Comprueba si N es divisible por un número que se compone de los dígitos del conjunto {A, B}

Dados tres números enteros N , A y B , la tarea es encontrar si N es divisible por cualquier número que contenga solo A y B como dígitos.

Ejemplos: 

Entrada: N = 106, a = 3, b = 5 
Salida: Sí 
106 es divisible por 53

Entrada: N = 107, a = 3, b = 5 
Salida: No 
  

Enfoque 1 (Recursivo): Una solución eficiente es hacer todos los números que contienen a y b como sus dígitos usando la función recursiva comenzando con los números a y b . Si la llamada a la función es fun(x) , entonces llame recursivamente a fun(x * 10 + a) y fun(x * 10 + b) . Si n es divisible por cualquiera de los números, imprima Sí ; de lo contrario, imprima No.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find if number N is divisible by a
// number that contains only a and b as it's digits
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether n is divisible
// by a number whose digits are either a or b
bool isDivisibleRec(int x, int a, int b, int n)
{
    // base condition
    if (x > n)
        return false;
 
    if (n % x == 0)
        return true;
 
    // recursive call
    return (isDivisibleRec(x * 10 + a, a, b, n)
            || isDivisibleRec(x * 10 + b, a, b, n));
}
 
bool isDivisible(int a, int b, int n)
{
   // Check for all numbers beginning with 'a' or 'b'
   return isDivisibleRec(a, a, b, n) ||
          isDivisibleRec(b, a, b, n);
}
 
// Driver program
int main()
{
    int a = 3, b = 5, n = 53;
 
    if (isDivisible(a, b, n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program to find if number N is divisible by a
// number that contains only a and b as it's digits
 
import java.util.*;
class solution
{
 
// Function to check whether n is divisible
// by a number whose digits are either a or b
static boolean isDivisibleRec(int x, int a, int b, int n)
{
    // base condition
    if (x > n)
        return false;
 
    if (n % x == 0)
        return true;
 
    // recursive call
    return (isDivisibleRec(x * 10 + a, a, b, n)
            || isDivisibleRec(x * 10 + b, a, b, n));
}
 
static boolean isDivisible(int a, int b, int n)
{
// Check for all numbers beginning with 'a' or 'b'
return isDivisibleRec(a, a, b, n)
        ||isDivisibleRec(b, a, b, n);
}
 
// Driver program
public static void main(String args[])
{
    int a = 3, b = 5, n = 53;
 
    if (isDivisible(a, b, n))
        System.out.print("Yes");
    else
        System.out.print("No");
 
}
 
}
//contributed by Arnab Kundu

# Python 3 program to find if number N
# is divisible by a number that contains
# only a and b as it's digits
 
# Function to check whether n is divisible
# by a number whose digits are either a or b
def isDivisibleRec(x, a, b, n):
 
    # base condition
    if (x > n):
        return False
 
    if (n % x == 0):
        return True
 
    # recursive call
    return (isDivisibleRec(x * 10 + a, a, b, n) or
            isDivisibleRec(x * 10 + b, a, b, n))
 
def isDivisible(a, b, n):
 
    # Check for all numbers beginning
    # with 'a' or 'b'
    return (isDivisibleRec(a, a, b, n) or
            isDivisibleRec(b, a, b, n))
 
# Driver Code
a = 3; b = 5; n = 53;
 
if (isDivisible(a, b, n)):
    print("Yes")
else:
    print("No")
 
# This code is contributed
# by Akanksha Rai

// C# program to find if number N is
// divisible by a number that contains
// only a and b as it's digits
using System;
 
class GFG
{
     
// Function to check whether n is divisible
// by a number whose digits are either a or b
static bool isDivisibleRec(int x, int a,
                           int b, int n)
{
    // base condition
    if (x > n)
        return false;
 
    if (n % x == 0)
        return true;
 
    // recursive call
    return (isDivisibleRec(x * 10 + a, a, b, n) ||
            isDivisibleRec(x * 10 + b, a, b, n));
}
 
static bool isDivisible(int a, int b, int n)
{
     
// Check for all numbers beginning
// with 'a' or 'b'
return isDivisibleRec(a, a, b, n) ||
       isDivisibleRec(b, a, b, n);
}
 
// Driver Code
static public void Main ()
{
    int a = 3, b = 5, n = 53;
 
    if (isDivisible(a, b, n))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
// This code is contributed by Sachin

<?php
// PHP program to find if number N is
// divisible by a number that contains
// only a and b as it's digits
 
// Function to check whether n is divisible
// by a number whose digits are either a or b
function isDivisibleRec($x, $a, $b, $n)
{
    // base condition
    if ($x > $n)
        return false;
 
    if ($n % $x == 0)
        return true;
 
    // recursive call
    return (isDivisibleRec($x * 10 + $a, $a, $b, $n) ||
            isDivisibleRec($x * 10 + $b, $a, $b, $n));
}
 
function isDivisible($a, $b, $n)
{
     
// Check for all numbers beginning
// with 'a' or 'b'
return isDivisibleRec($a, $a, $b, $n) ||
       isDivisibleRec($b, $a, $b, $n);
}
 
// Driver Code
$a = 3; $b = 5; $n = 53;
 
if (isDivisible($a, $b, $n))
    echo "Yes";
else
    echo "No";
 
// This code is contributed
// by Akanksha Rai

<script>
 
// Javascript program to find if number
// N is divisible by a number that
// contains only a and b as it's digits
 
// Function to check whether n is divisible
// by a number whose digits are either a or b
function isDivisibleRec(x, a, b, n)
{
     
    // Base condition
    if (x > n)
        return false;
 
    if (n % x == 0)
        return true;
 
    // Recursive call
    return(isDivisibleRec(x * 10 + a, a, b, n) ||
           isDivisibleRec(x * 10 + b, a, b, n));
}
 
function isDivisible(a, b, n)
{
     
    // Check for all numbers beginning
    // with 'a' or 'b'
    return isDivisibleRec(a, a, b, n) ||
           isDivisibleRec(b, a, b, n);
}
 
// Driver code
let a = 3, b = 5, n = 53;
 
if (isDivisible(a, b, n))
    document.write("Yes");
else
    document.write("No");
     
// This code is contributed by souravmahato348
 
</script>

Yes

Enfoque 2 (basado en cola): la idea es generar todos los números (menores que n) que contengan dígitos a y b. Para cada número, comprueba si divide a n o no. ¿Cómo generar todos los números más pequeños que n? Usamos la cola para esto. Inicialmente empujamos ‘a’ y ‘b’ a la cola. Luego ejecutamos un ciclo mientras el frente de la cola es más pequeño que n. Abrimos un elemento uno por uno y, para siempre, abrimos el elemento x, generamos los siguientes números x * 10 + a y x * 10 + b y los ponemos en cola. La complejidad de tiempo de este enfoque es O(n).
Consulte la publicación a continuación para ver la implementación de este enfoque. 
Recuento de números de dígitos binarios menores que N