Número más pequeño de N dígitos sin ninguno de sus dígitos como divisor

Dado un número entero N . La tarea es encontrar el número S de N dígitos más pequeño , tal que S no sea divisible por ninguno de sus dígitos. Imprima -1 si tal número no es posible.
Ejemplos: 

Entrada: N = 2 
Salida: 23 
Explicación: 23 es el número más pequeño de dos dígitos que no es divisible por ninguno de sus dígitos.
Entrada: N = 1 
Salida: -1 
Explicación: Cada número de un solo dígito es divisible por sí mismo.
Entrada: N = 4 
Salida: 2227 
Explicación: 2227 es el número de cuatro dígitos más pequeño que no es divisible por ninguno de sus dígitos. 
 

Acercarse: 

• El enfoque es encontrar el número de N dígitos más pequeño y más grande posible, digamos que estos números son L y R respectivamente.
• Iterar sobre el rango [L, R] .
• Para cada número en el rango, extraiga cada dígito de ese número y verifique si el número es divisible por ese dígito.
• Si al menos un dígito del número lo divide, descarta ese número e itera para verificar el siguiente número.
• Si ninguno de los dígitos de ese número lo divide, imprima ese número y salga del bucle. Este número así encontrado es el número más pequeño.

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

// C++ Program for the given problem
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate power
int power(int a, int b)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return a;
 
    int tmp = power(a, b / 2);
 
    int result = tmp * tmp;
 
    if (b % 2 == 1)
        result *= a;
 
    return result;
}
 
// Function to check if the
// N-digit number satisfies the
// given condition or not
bool check(int n)
{
    int temp = n;
    while (temp > 0) {
 
        // Getting the last digit
        int last_digit = temp % 10;
 
        // Every number is divisible
        // by 1 and dividing a number
        // by 0 isn't possible. Thus
        // numbers with 0 as a digit
        // must be discarded.
        if (last_digit == 0
            || last_digit == 1)
            return false;
 
        // If any digit divides the
        // number, return false
        if (n % last_digit == 0)
            return false;
        temp = temp / 10;
    }
 
    // If no digit divides the
    // number, return true;
    return true;
}
 
// Function to find the smallest
// number not divisible by any
// of its digits.
void solve(int n)
{
    // Get the lower range of n
    // digit number
    int L = power(10, n - 1);
 
    // Get the high range of n
    // digit number
    int R = power(10, n) - 1;
 
    int flag = 0;
 
    // check all the N-digit numbers
    for (int i = L; i <= R; i++) {
 
        bool answer = check(i);
 
        // If the first number to satisfy
        // the constraints is found
        // print it, set the flag value
        // and break out of the loop.
        if (answer == true) {
 
            cout << i << endl;
            flag++;
            break;
        }
    }
 
    // If no such digit found,
    // return -1 as per problem statement
    if (flag == 0)
        cout << -1 << endl;
}
 
// Driver Code
int main()
{
    int N = 4;
    solve(N);
}

// Java program for the given problem
import java.util.*;
 
class GFG{
     
// Function to calculate power
static int power(int a, int b)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return a;
         
    int tmp = power(a, b / 2);
    int result = tmp * tmp;
     
    if (b % 2 == 1)
        result *= a;
 
    return result;
}
 
// Function to check if the
// N-digit number satisfies the
// given condition or not
static boolean check(int n)
{
    int temp = n;
    while (temp > 0)
    {
         
        // Getting the last digit
        int last_digit = temp % 10;
         
        // Every number is divisible
        // by 1 and dividing a number
        // by 0 isn't possible. Thus
        // numbers with 0 as a digit
        // must be discarded.
        if (last_digit == 0 ||
            last_digit == 1)
            return false;
             
        // If any digit divides the
        // number, return false
        if (n % last_digit == 0)
            return false;
        temp = temp / 10;
    }
     
    // If no digit divides the
    // number, return true;
    return true;
}
 
// Function to find the smallest
// number not divisible by any
// of its digits.
static void solve(int n)
{
     
    // Get the lower range of n
    // digit number
    int L = power(10, n - 1);
     
    // Get the high range of n
    // digit number
    int R = power(10, n) - 1;
     
    int flag = 0;
     
    // Check all the N-digit numbers
    for(int i = L; i <= R; i++)
    {
        boolean answer = check(i);
         
        // If the first number to satisfy
        // the constraints is found
        // print it, set the flag value
        // and break out of the loop.
        if (answer == true)
        {
            System.out.println(i);
            flag++;
            break;
        }
    }
     
    // If no such digit found,
    // return -1 as per problem statement
    if (flag == 0)
    System.out.println("-1");
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4;
     
    solve(N);
}
}
 
// This code is contributed by offbeat

# Python3 Program for the
# given problem
 
# Function to calculate
# power
def power(a, b):
 
    if (b == 0):
        return 1;
    if (b == 1):
        return a;
  
    tmp = power(a, b // 2); 
    result = tmp * tmp;
  
    if (b % 2 == 1):
        result *= a;
  
    return result;
 
# Function to check if the
# N-digit number satisfies the
# given condition or not
def check(n):
 
    temp = n;
    while (temp > 0):
  
        # Getting the last digit
        last_digit = temp % 10;
  
        # Every number is divisible
        # by 1 and dividing a number
        # by 0 isn't possible. Thus
        # numbers with 0 as a digit
        # must be discarded.
        if (last_digit == 0 or
            last_digit == 1):
            return False;
  
        # If any digit divides the
        # number, return false
        if (n % last_digit == 0):
            return False;
             
        temp = temp // 10;    
  
    # If no digit divides the
    # number, return true;
    return True;
 
# Function to find the smallest
# number not divisible by any
# of its digits.
def solve(n):
 
    # Get the lower range of n
    # digit number
    L = power(10, n - 1);
  
    # Get the high range of n
    # digit number
    R = power(10, n) - 1;
  
    flag = 0;
  
    # check all the N-digit
    # numbers
    for i in range(L, R + 1):
        answer = check(i);
  
        # If the first number to satisfy
        # the constraints is found
        # print it, set the flag value
        # and break out of the loop.
        if (answer):           
            print(i)
            flag += 1;
            break;
         
    # If no such digit found,
    # return -1 as per problem
    # statement
    if (flag == 0):
        print(-1)
         
# Driver code
if __name__ == "__main__":
     
    N = 4;
    solve(N);
 
# This code is contributed by rutvik_56

// C# program for the given problem
using System;
 
class GFG{
     
// Function to calculate power
static int power(int a, int b)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return a;
         
    int tmp = power(a, b / 2);
    int result = tmp * tmp;
     
    if (b % 2 == 1)
        result *= a;
 
    return result;
}
 
// Function to check if the
// N-digit number satisfies the
// given condition or not
static bool check(int n)
{
    int temp = n;
    while (temp > 0)
    {
         
        // Getting the last digit
        int last_digit = temp % 10;
         
        // Every number is divisible
        // by 1 and dividing a number
        // by 0 isn't possible. Thus
        // numbers with 0 as a digit
        // must be discarded.
        if (last_digit == 0 ||
            last_digit == 1)
            return false;
             
        // If any digit divides the
        // number, return false
        if (n % last_digit == 0)
            return false;
        temp = temp / 10;
    }
     
    // If no digit divides the
    // number, return true;
    return true;
}
 
// Function to find the smallest
// number not divisible by any
// of its digits.
static void solve(int n)
{
     
    // Get the lower range of n
    // digit number
    int L = power(10, n - 1);
     
    // Get the high range of n
    // digit number
    int R = power(10, n) - 1;
     
    int flag = 0;
     
    // Check all the N-digit numbers
    for(int i = L; i <= R; i++)
    {
        bool answer = check(i);
         
        // If the first number to satisfy
        // the constraints is found
        // print it, set the flag value
        // and break out of the loop.
        if (answer == true)
        {
            Console.WriteLine(i);
            flag++;
            break;
        }
    }
     
    // If no such digit found,
    // return -1 as per problem statement
    if (flag == 0)
    Console.WriteLine("-1");
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 4;
     
    solve(N);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaSCript Program for the given problem
 
// Function to calculate power
function power(a, b)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return a;
 
    let tmp = power(a, Math.floor(b / 2));
 
    let result = tmp * tmp;
 
    if (b % 2 == 1)
        result *= a;
 
    return result;
}
 
// Function to check if the
// N-digit number satisfies the
// given condition or not
function check(n)
{
    let temp = n;
    while (temp > 0) {
 
        // Getting the last digit
        let last_digit = temp % 10;
 
        // Every number is divisible
        // by 1 and dividing a number
        // by 0 isn't possible. Thus
        // numbers with 0 as a digit
        // must be discarded.
        if (last_digit == 0
            || last_digit == 1)
            return false;
 
        // If any digit divides the
        // number, return false
        if (n % last_digit == 0)
            return false;
        temp = Math.floor(temp / 10);
    }
 
    // If no digit divides the
    // number, return true;
    return true;
}
 
// Function to find the smallest
// number not divisible by any
// of its digits.
function solve(n)
{
    // Get the lower range of n
    // digit number
    let L = power(10, n - 1);
 
    // Get the high range of n
    // digit number
    let R = power(10, n) - 1;
 
    let flag = 0;
 
    // check all the N-digit numbers
    for (let i = L; i <= R; i++) {
 
        let answer = check(i);
 
        // If the first number to satisfy
        // the constraints is found
        // print it, set the flag value
        // and break out of the loop.
        if (answer === true) {
 
            document.write(i + "<br>");
            flag++;
            break;
        }
    }
 
    // If no such digit found,
    // return -1 as per problem statement
    if (flag === 0)
        document.write("-1" + "<br>");
}
 
// Driver Code
 
    let N = 4;
    solve(N);
 
// This code is contributed by Surbhi Tyagi.
 
</script>

2227

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)