Número más pequeño de K dígitos divisible por todos los números en una array dada

Dada una array arr[] . La tarea es crear el número de dígitos K más pequeño divisible por todos los números de arr[] .

Ejemplos:

Entrada: arr[] = {2, 3, 5}, N = 3
Salida: 120
Explicación: 120 es divisible por 2, 3 y 5

Entrada: arr[] = {2, 6, 7, 4, 5}, N = 5
Salida: 10080

Enfoque: Este problema se puede resolver usando Mínimo común múltiplo . Siga los pasos a continuación para resolver el problema dado. 

• Encuentre el LCM de todos los elementos de la array de arr[] .
• Encuentre un múltiplo de MCM que tenga K dígitos.
• El primer número que tenga K dígitos será la respuesta final.
• Finalmente, devuelva la respuesta.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive implementation
int findLCM(vector<int> arr, int idx)
{
    // lcm(a,b) = (a*b/gcd(a,b))
    if (idx == arr.size() - 1) {
        return arr[idx];
    }
    int a = arr[idx];
    int b = findLCM(arr, idx + 1);
   
    return (a * b / __gcd(a, b));
}
 
// Finding smallest number with given conditions
int findNum(vector<int>& arr, int N)
{
    int lcm = findLCM(arr, 0);
    int ans = pow(10, N - 1) / lcm;
    ans = (ans + 1) * lcm;
    return ans;
}
 
// Driver Code
int main()
{
      // Array arr[]
    vector<int> arr = { 2, 3, 5 };
    int N = 3;
   
      // Function call
    cout << findNum(arr, N);
   
    return 0;
}

// Java program for above approach
class GFG {
 
  static int __gcd(int a, int b) {
 
    // Everything divides 0
    if (b == 0) {
      return a;
    }
 
    return __gcd(b, a % b);
  }
 
  // Recursive implementation
  static int findLCM(int[] arr, int idx)
  {
 
    // lcm(a,b) = (a*b/gcd(a,b))
    if (idx == arr.length - 1) {
      return arr[idx];
    }
    int a = arr[idx];
    int b = findLCM(arr, idx + 1);
 
    return (a * b / __gcd(a, b));
  }
 
  // Finding smallest number with given conditions
  static int findNum(int[] arr, int N) {
    int lcm = findLCM(arr, 0);
    int ans = (int) Math.pow(10, N - 1) / lcm;
    ans = (ans + 1) * lcm;
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
 
    // Array arr[]
    int[] arr = { 2, 3, 5 };
    int N = 3;
 
    // Function call
    System.out.println(findNum(arr, N));
 
  }
}
 
// This code is contributed b saurabh_jaiswal.

# Python 3 program for above approach
import math
# Recursive implementation
def findLCM(arr, idx):
 
    # lcm(a,b) = (a*b/gcd(a,b))
    if (idx == len(arr) - 1):
        return arr[idx]
 
    a = arr[idx]
    b = findLCM(arr, idx + 1)
 
    return (a * b // math.gcd(a, b))
 
# Finding smallest number with given conditions
 
 
def findNum(arr, N):
 
    lcm = findLCM(arr, 0)
    ans = pow(10, N - 1) // lcm
    ans = (ans + 1) * lcm
    return ans
 
 
# Driver Code
if __name__ == "__main__":
 
    # Array arr[]
    arr = [2, 3, 5]
    N = 3
 
    # Function call
    print(findNum(arr, N))
 
    # This code is contributed by ukasp.

// C# program for above approach
using System;
class GFG {
 
  static int __gcd(int a, int b) {
 
    // Everything divides 0
    if (b == 0) {
      return a;
    }
 
    return __gcd(b, a % b);
  }
 
  // Recursive implementation
  static int findLCM(int[] arr, int idx)
  {
 
    // lcm(a,b) = (a*b/gcd(a,b))
    if (idx == arr.Length - 1) {
      return arr[idx];
    }
    int a = arr[idx];
    int b = findLCM(arr, idx + 1);
 
    return (a * b / __gcd(a, b));
  }
 
  // Finding smallest number with given conditions
  static int findNum(int[] arr, int N) {
    int lcm = findLCM(arr, 0);
    int ans = (int) Math.Pow(10, N - 1) / lcm;
    ans = (ans + 1) * lcm;
    return ans;
  }
 
  // Driver Code
  public static void Main(string []args)
  {
 
    // Array arr[]
    int[] arr = { 2, 3, 5 };
    int N = 3;
 
    // Function call
    Console.WriteLine(findNum(arr, N));
 
  }
}
 
// This code is contributed by gaurav01.

<script>
        // JavaScript code for the above approach
        function __gcd(a, b) {
 
            // Everything divides 0
            if (b == 0) {
                return a;
            }
 
            return __gcd(b, a % b);
        }
         
        // Recursive implementation
        function findLCM(arr, idx)
        {
         
            // lcm(a,b) = (a*b/gcd(a,b))
            if (idx == arr.length - 1) {
                return arr[idx];
            }
            let a = arr[idx];
            let b = findLCM(arr, idx + 1);
 
            return (a * b / __gcd(a, b));
        }
 
        // Finding smallest number with given conditions
        function findNum(arr, N) {
            let lcm = findLCM(arr, 0);
            let ans = Math.floor(Math.pow(10, N - 1) / lcm);
            ans = (ans + 1) * lcm;
            return ans;
        }
 
        // Driver Code
 
        // Array arr[]
        let arr = [2, 3, 5];
        let N = 3;
 
        // Function call
        document.write(findNum(arr, N));
 
  // This code is contributed by Potta Lokesh
    </script>

120

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