Given an array arr[]. The task is to create the smallest K digit number divisible by all numbers of arr[].
Examples:
Input: arr[] = {2, 3, 5}, N = 3
Output: 120
Explanation: 120 is divisible by 2, 3 and 5Input: arr[] = {2, 6, 7, 4, 5}, N = 5
Output: 10080
Recursive approach: This problem can be solved by using Lowest common multiple. Follow the steps below to solve the given problem.
- Find the LCM of all the array elements of arr[].
- Find a multiple of LCM having K digits.
- The first number having K digits will be the final answer.
- Finally, return the answer.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Recursive implementationint 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 conditionsint 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 Codeint main(){ // Array arr[] vector<int> arr = { 2, 3, 5 }; int N = 3; // Function call cout << findNum(arr, N); return 0;} |
Java
// Java program for above approachclass 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. |
Python3
# Python 3 program for above approachimport math# Recursive implementationdef 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 conditionsdef findNum(arr, N): lcm = findLCM(arr, 0) ans = pow(10, N - 1) // lcm ans = (ans + 1) * lcm return ans# Driver Codeif __name__ == "__main__": # Array arr[] arr = [2, 3, 5] N = 3 # Function call print(findNum(arr, N)) # This code is contributed by ukasp. |
C#
// C# program for above approachusing 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. |
Javascript
<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> |
Output
120
Time Complexity: O(N)
Auxiliary Space: O(1)
Method 2: Iterative Approach
- Initialize a variable num to the smallest K digit number, which is 10^(K-1).
- Create a loop that continues until we find a number that is divisible by all the numbers in the array.
- Inside the loop, check if num is divisible by all the numbers in the array using the all() function in Python. If it is divisible, then we have found the required number and we can return it.
- If num is not divisible by all the numbers in the array, increment it by 1 and continue the loop.
- Return the smallest number that is divisible by all the numbers in the array.
C++
#include <iostream>#include <vector>#include <cmath>using namespace std;int smallest_k_digit_num_divisible_by_all(vector<int> arr, int k) { int num = pow(10, k - 1); // smallest K digit number while (true) { bool is_divisible = true; for (int n : arr) { if (num % n != 0) { is_divisible = false; break; } } if (is_divisible) { return num; } num++; }}int main() { vector<int> arr = {2, 3, 5, 7}; int k = 4; int num = smallest_k_digit_num_divisible_by_all(arr, k); cout << num << endl; return 0;} |
Java
import java.util.*;public class Main { public static int smallestKDigitNumDivisibleByAll(List<Integer> arr, int k) { int num = (int) Math.pow(10, k - 1); // smallest K digit number while (true) { boolean isDivisible = true; for (int n : arr) { if (num % n != 0) { isDivisible = false; break; } } if (isDivisible) { return num; } num++; } } public static void main(String[] args) { List<Integer> arr = new ArrayList<>(Arrays.asList(2, 3, 5, 7)); int k = 4; int num = smallestKDigitNumDivisibleByAll(arr, k); System.out.println(num); }} |
Python3
def smallest_k_digit_num_divisible_by_all(arr, k): num = 10 ** (k - 1) # smallest K digit number while True: if all(num % n == 0 for n in arr): return num num += 1# example usagearr = [2, 3, 5, 7]k = 4num = smallest_k_digit_num_divisible_by_all(arr, k)print(num) |
C#
using System;using System.Collections.Generic;class SmallestNumberDivisibleByAll { static int SmallestKDigitNumDivisibleByAll(List<int> arr, int k) { int num = (int)Math.Pow( 10, k - 1); // smallest K digit number while (true) { bool isDivisible = true; foreach(int n in arr) { if (num % n != 0) { isDivisible = false; break; } } if (isDivisible) { return num; } num++; } } static void Main() { List<int> arr = new List<int>{ 2, 3, 5, 7 }; int k = 4; int num = SmallestKDigitNumDivisibleByAll(arr, k); Console.WriteLine(num); }}// This code is contributed by sarojmcy2e |
Javascript
function smallest_k_digit_num_divisible_by_all(arr, k) { let num = Math.pow(10, k - 1); // smallest K digit number while (true) { let is_divisible = true; for (let n of arr) { if (num % n != 0) { is_divisible = false; break; } } if (is_divisible) { return num; } num++; }}let arr = [2, 3, 5, 7];let k = 4;let num = smallest_k_digit_num_divisible_by_all(arr, k);console.log(num); |
Output
1050
Time complexity: O(N * K), where N is the number of elements in the input array and K is the number of digits in the smallest number that we need to find.
Auxiliary space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
