Número más pequeño no menor que N que es divisible por todos los dígitos de N

Dado un entero positivo N , la tarea es encontrar el entero más pequeño mayor o igual a X , que tenga todos sus dígitos divisibles por los dígitos distintos de cero de N .

Ejemplos:

Entrada: N = 280
Salida: 280
Explicación:
280 es el más pequeño que es divisible por los dígitos 8 y 2.

Entrada: N = 32
Salida: 36
Explicación:
36 es el número más pequeño que es divisible por los dígitos 2 y 3.

Enfoque: La idea es encontrar el MCM de todos los dígitos distintos de cero de X y luego encontrar el siguiente múltiplo mayor de ese valor de MCM que es mayor que N .

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

// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
 
// Function to calculate the LCM
int LCM(int A, int B)
{
    return (A * B / __gcd(A, B));
}
 
// Function to find the smallest number
// satisfying given constraints
int findSmallestNumber(int X)
{
    // LCM value is 1 initially
    int lcm = 1;
    int temp = X;
 
    // Finding the LCM of all
    // non zero digits
    while (temp) {
 
        int last = temp % 10;
        temp /= 10;
 
        if (!last)
            continue;
 
        // Update the value lcm
        lcm = LCM(lcm, last);
    }
 
    // Stores ceil value
    int answer = ((X + lcm - 1) / lcm)
                 * lcm;
 
    // Print the answer
    cout << answer;
}
 
// Driver Code
int main()
{
    int X = 280;
 
    // Function Call
    findSmallestNumber(X);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
  // Function to calculate the LCM
  static int LCM(int A, int B)
  {
    return (A * B / __gcd(A, B));
  }
 
  // Function to find the smallest number
  // satisfying given constraints
  static void findSmallestNumber(int X)
  {
 
    // LCM value is 1 initially
    int lcm = 1;
    int temp = X;
 
    // Finding the LCM of all
    // non zero digits
    while (temp > 0)
    {
      int last = temp % 10;
      temp /= 10;
 
      if (last == 0)
        continue;
 
      // Update the value lcm
      lcm = LCM(lcm, last);
    }
 
    // Stores ceil value
    int answer = ((X + lcm - 1) / lcm)
      * lcm;
 
    // Print the answer
    System.out.print(answer);
 
  }
  static int __gcd(int a, int b) 
  { 
    return b == 0 ? a:__gcd(b, a % b);    
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int X = 280;
 
    // Function Call
    findSmallestNumber(X);
  }
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
import math
 
# Function to calculate the LCM
def LCM(A, B):
     
    return (A * B // math.gcd(A, B))
 
# Function to find the smallest number
# satisfying given constraints
def findSmallestNumber(X):
     
    # LCM value is 1 initially
    lcm = 1
    temp = X
 
    # Finding the LCM of all
    # non zero digits
    while (temp):
        last = temp % 10
        temp //= 10
 
        if (not last):
            continue
 
        # Update the value lcm
        lcm = LCM(lcm, last)
 
    # Stores ceil value
    answer = ((X + lcm - 1) // lcm) * lcm
 
    # Print the answer
    print(answer)
 
# Driver Code
if __name__ == "__main__":
     
    X = 280
 
    # Function Call
    findSmallestNumber(X)
 
# This code is contributed by chitranayal

// C# program for the above approach
using System;
class GFG{
 
  // Function to calculate the LCM
  static int LCM(int A, int B)
  {
    return (A * B / __gcd(A, B));
  }
 
  // Function to find the smallest number
  // satisfying given constraints
  static void findSmallestNumber(int X)
  {
 
    // LCM value is 1 initially
    int lcm = 1;
    int temp = X;
 
    // Finding the LCM of all
    // non zero digits
    while (temp > 0)
    {
      int last = temp % 10;
      temp /= 10;
 
      if (last == 0)
        continue;
 
      // Update the value lcm
      lcm = LCM(lcm, last);
    }
 
    // Stores ceil value
    int answer = ((X + lcm - 1) / lcm)
      * lcm;
 
    // Print the answer
    Console.Write(answer);
 
  }
  static int __gcd(int a, int b) 
  { 
    return b == 0 ? a:__gcd(b, a % b);    
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int X = 280;
 
    // Function Call
    findSmallestNumber(X);
  }
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program for the above approach
 
// Function to calculate the LCM
function LCM(A,B)
{
    return (A * B / __gcd(A, B));
}
 
// Function to find the smallest number
  // satisfying given constraints
function findSmallestNumber(X)
{
    // LCM value is 1 initially
    let lcm = 1;
    let temp = X;
  
    // Finding the LCM of all
    // non zero digits
    while (temp > 0)
    {
      let last = temp % 10;
      temp = Math.floor(temp/10);
  
      if (last == 0)
        continue;
  
      // Update the value lcm
      lcm = LCM(lcm, last);
    }
  
    // Stores ceil value
    let answer = Math.floor((X + lcm - 1) / lcm)
      * lcm;
  
    // Print the answer
    document.write(answer);
}
 
function __gcd(a,b)
{
    return b == 0 ? a:__gcd(b, a % b);
}
 
 // Driver Code
let X = 280;
 
// Function Call
findSmallestNumber(X);
 
 
// This code is contributed by rag2127
 
</script>

280

Complejidad de tiempo: O(N*log ₁₀ N)
Espacio auxiliar: O(1)