Given x, y, z and n, find smallest n digit number which is divisible by x, y and z.
Examples:
Input : x = 2, y = 3, z = 5
n = 4
Output : 1020
Input : x = 3, y = 5, z = 7
n = 2
Output : Not possible
Method: Brute-force
The brute-force approach to solve this problem is as follows
- Define a function is_divisible_by_xyz(number, x, y, z) that takes a number and three other numbers x, y, and z as input and returns True if the number is divisible by all three of them, and False otherwise.
- Define a function smallest_n_digit_number(x, y, z, n) that takes three numbers x, y, and z and an integer n as input and returns the smallest n-digit number that is divisible by all three of them.
- Inside the function smallest_n_digit_number(x, y, z, n), set the lower and upper limits for n-digit numbers as 10^(n-1) and 10^n-1, respectively.
- Use a for loop to iterate through all n-digit numbers in the range [lower_limit, upper_limit] and check if each number is divisible by x, y, and z by calling the function is_divisible_by_xyz(number, x, y, z).
- If a number divisible by x, y, and z is found, return it.
- If no such number is found, return -1.
C++
#include <iostream>#include <cmath>using namespace std;// Function to check if a number is divisible by x, y, and zbool isDivisibleByXYZ(int number, int x, int y, int z) { return number % x == 0 && number % y == 0 && number % z == 0;}// Function to find the smallest n-digit number which is divisible by x, y, and zint smallestNDigitNumber(int x, int y, int z, int n) { // Setting the lower and upper limits for n-digit numbers int lowerLimit = pow(10, n - 1); int upperLimit = pow(10, n) - 1; // Iterating through all n-digit numbers and checking if they are divisible by x, y, and z for (int number = lowerLimit; number <= upperLimit; number++) { if (isDivisibleByXYZ(number, x, y, z)) { return number; } } // If no n-digit number divisible by x, y, and z is found, return -1 return -1;}// Driver codeint main() { int x = 2; int y = 3; int z = 5; int n = 4; cout << smallestNDigitNumber(x, y, z, n) << endl; // Output: 1020 return 0;} |
Java
public class SmallestNDigitNumber { // Function to check if a number is divisible by x, y, and z static boolean isDivisibleByXYZ(int number, int x, int y, int z) { return number % x == 0 && number % y == 0 && number % z == 0; } // Function to find the smallest n-digit number which is divisible by x, y, and z static int smallestNDigitNumber(int x, int y, int z, int n) { // Setting the lower and upper limits for n-digit numbers int lowerLimit = (int) Math.pow(10, n - 1); int upperLimit = (int) Math.pow(10, n) - 1; // Iterating through all n-digit numbers and checking if // they are divisible by x, y, and z for (int number = lowerLimit; number <= upperLimit; number++) { if (isDivisibleByXYZ(number, x, y, z)) { return number; } } // If no n-digit number divisible by x, y, and z is found, return -1 return -1; } // Driver code public static void main(String[] args) { int x = 2; int y = 3; int z = 5; int n = 4; System.out.println(smallestNDigitNumber(x, y, z, n)); // Output: 1020 }} |
Python3
# Function to check if a number is divisible by x, y, and zdef is_divisible_by_xyz(number, x, y, z): return number % x == 0 and number % y == 0 and number % z == 0# Function to find the smallest n-digit number# which is divisible by x, y, and zdef smallest_n_digit_number(x, y, z, n): # Setting the lower and upper limits for n-digit numbers lower_limit = 10**(n-1) upper_limit = 10**n - 1 # Iterating through all n-digit numbers and checking if they are divisible by x, y, and z for number in range(lower_limit, upper_limit+1): if is_divisible_by_xyz(number, x, y, z): return number # If no n-digit number divisible by x, y, and z is found, return -1 return -1 # Driver codex = 2y = 3z = 5n = 4print(smallest_n_digit_number(x, y, z, n)) # Output: 1020 |
Javascript
// Function to check if a number is divisible by x, y, and zfunction is_divisible_by_xyz(number, x, y, z) { return number % x === 0 && number % y === 0 && number % z === 0;}// Function to find the smallest n-digit number// which is divisible by x, y, and zfunction smallest_n_digit_number(x, y, z, n) { // Setting the lower and upper limits for n-digit numbers const lower_limit = 10**(n-1); const upper_limit = 10**n - 1; // Iterating through all n-digit numbers and checking // if they are divisible by x, y, and z for (let number = lower_limit; number <= upper_limit; number++) { if (is_divisible_by_xyz(number, x, y, z)) { return number; } } // If no n-digit number divisible by x, y, and z is found, return -1 return -1;}// Driver codeconst x = 2;const y = 3;const z = 5;const n = 4;console.log(smallest_n_digit_number(x, y, z, n)); // Output: 1020 |
Output
1020
Time complexity: O(10^n), where n is the number of digits in the required number.
Auxiliary space: O(1)
Method 2:
1) Find smallest n digit number is pow(10, n-1).
2) Find LCM of given 3 numbers x, y and z.
3) Find remainder of the LCM when divided by pow(10, n-1).
4) Add the “LCM – remainder” to pow(10, n-1). If this addition is still a n digit number, we return the result. Else we return Not possible.
Illustration :
Suppose n = 4 and x, y, z are 2, 3, 5 respectively.
1) First find the least four digit number i.e. 1000,
2) LCM of 2, 3, 5 so the LCM is 30.
3) Find the remainder of 1000 % 30 = 10
4) Subtract the remainder from LCM, 30 – 10 = 20. Result is 1000 + 20 = 1020.
Below is the implementation of above approach:
C++
// C++ program to find smallest n digit number// which is divisible by x, y and z.#include <bits/stdc++.h>using namespace std;// LCM for x, y, zint LCM(int x, int y, int z){ int ans = ((x * y) / (__gcd(x, y))); return ((z * ans) / (__gcd(ans, z)));}// returns smallest n digit number divisible// by x, y and zint findDivisible(int n, int x, int y, int z){ // find the LCM int lcm = LCM(x, y, z); // find power of 10 for least number int ndigitnumber = pow(10, n-1); // reminder after int reminder = ndigitnumber % lcm; // If smallest number itself divides // lcm. if (reminder == 0) return ndigitnumber; // add lcm- reminder number for // next n digit number ndigitnumber += lcm - reminder; // this condition check the n digit // number is possible or not // if it is possible it return // the number else return 0 if (ndigitnumber < pow(10, n)) return ndigitnumber; else return 0;}// driver codeint main(){ int n = 4, x = 2, y = 3, z = 5; int res = findDivisible(n, x, y, z); // if number is possible then // it print the number if (res != 0) cout << res; else cout << "Not possible"; return 0;} |
Java
// Java program to find smallest n digit number// which is divisible by x, y and z.import java.io.*;public class GFG { static int __gcd(int a, int b) { if (b == 0) { return a; } else { return __gcd(b, a % b); } } // LCM for x, y, z static int LCM(int x, int y, int z) { int ans = ((x * y) / (__gcd(x, y))); return ((z * ans) / (__gcd(ans, z))); } // returns smallest n digit number // divisible by x, y and z static int findDivisible(int n, int x, int y, int z) { // find the LCM int lcm = LCM(x, y, z); // find power of 10 for least number int ndigitnumber = (int)Math.pow(10, n - 1); // reminder after int reminder = ndigitnumber % lcm; // If smallest number itself divides // lcm. if (reminder == 0) return ndigitnumber; // add lcm- reminder number for // next n digit number ndigitnumber += lcm - reminder; // this condition check the n digit // number is possible or not // if it is possible it return // the number else return 0 if (ndigitnumber < Math.pow(10, n)) return ndigitnumber; else return 0; } // driver code static public void main(String[] args) { int n = 4, x = 2, y = 3, z = 5; int res = findDivisible(n, x, y, z); // if number is possible then // it print the number if (res != 0) System.out.println(res); else System.out.println("Not possible"); }}// This code is contributed by vt_m. |
Python3
# Python3 code to find smallest n digit # number which is divisible by x, y and z.from fractions import gcdimport math# LCM for x, y, zdef LCM( x , y , z ): ans = int((x * y) / (gcd(x, y))) return int((z * ans) / (gcd(ans, z))) # returns smallest n digit number # divisible by x, y and zdef findDivisible (n, x, y, z): # find the LCM lcm = LCM(x, y, z) # find power of 10 for least number ndigitnumber = math.pow(10, n-1) # reminder after reminder = ndigitnumber % lcm # If smallest number itself # divides lcm. if reminder == 0: return ndigitnumber # add lcm- reminder number for # next n digit number ndigitnumber += lcm - reminder # this condition check the n digit # number is possible or not # if it is possible it return # the number else return 0 if ndigitnumber < math.pow(10, n): return int(ndigitnumber) else: return 0# driver coden = 4x = 2y = 3z = 5res = findDivisible(n, x, y, z)# if number is possible then # it print the numberif res != 0: print( res)else: print("Not possible") # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to find smallest n digit number// which is divisible by x, y and z.using System;public class GFG{ static int __gcd(int a, int b) { if(b == 0) { return a; } else { return __gcd(b, a % b); } } // LCM for x, y, z static int LCM(int x, int y, int z) { int ans = ((x * y) / (__gcd(x, y))); return ((z * ans) / (__gcd(ans, z))); } // returns smallest n digit number divisible // by x, y and z static int findDivisible(int n, int x, int y, int z) { // find the LCM int lcm = LCM(x, y, z); // find power of 10 for least number int ndigitnumber =(int)Math. Pow(10, n - 1); // reminder after int reminder = ndigitnumber % lcm; // If smallest number itself divides // lcm. if (reminder == 0) return ndigitnumber; // add lcm- reminder number for // next n digit number ndigitnumber += lcm - reminder; // this condition check the n digit // number is possible or not // if it is possible it return // the number else return 0 if (ndigitnumber < Math.Pow(10, n)) return ndigitnumber; else return 0; } // Driver code static public void Main () { int n = 4, x = 2, y = 3, z = 5; int res = findDivisible(n, x, y, z); // if number is possible then // it print the number if (res != 0) Console.WriteLine(res); else Console.WriteLine("Not possible"); }}// This code is contributed by vt_m. |
Javascript
<script>// JavaScript program to find smallest n digit number// which is divisible by x, y and z. function __gcd(a, b) { if(b == 0) { return a; } else { return __gcd(b, a % b); } } // LCM for x, y, z function LCM(x, y, z) { let ans = ((x * y) / (__gcd(x, y))); return ((z * ans) / (__gcd(ans, z))); } // returns smallest n digit number divisible // by x, y and z function findDivisible(n, x, y, z) { // find the LCM let lcm = LCM(x, y, z); // find power of 10 for least number let ndigitnumber = Math.pow(10, n - 1); // reminder after let reminder = ndigitnumber % lcm; // If smallest number itself divides // lcm. if (reminder == 0) return ndigitnumber; // add lcm- reminder number for // next n digit number ndigitnumber += lcm - reminder; // this condition check the n digit // number is possible or not // if it is possible it return // the number else return 0 if (ndigitnumber < Math.pow(10, n)) return ndigitnumber; else return 0; } // Driver Code let n = 4, x = 2, y = 3, z = 5; let res = findDivisible(n, x, y, z); // if number is possible then // it print the number if (res != 0) document.write(res); else document.write("Not possible"); // This code is contributed by chinmoy1997pal.</script> |
PHP
<?php// php program to find smallest n digit number// which is divisible by x, y and z.// gcd functionfunction gcd($a, $b) { return ($a % $b) ? gcd($b, $a % $b) : $b;}// LCM for x, y, zfunction LCM($x, $y, $z){ $ans = floor(($x * $y) / (gcd($x, $y))); return floor(($z * $ans) / (gcd($ans, $z)));}// returns smallest n digit number divisible// by x, y and zfunction findDivisible($n, $x, $y, $z){ // find the LCM $lcm = LCM($x, $y, $z); // find power of 10 for least number $ndigitnumber = pow(10, $n-1); // reminder after $reminder = $ndigitnumber % $lcm; // If smallest number itself divides // lcm. if ($reminder == 0) return $ndigitnumber; // add lcm- reminder number for // next n digit number $ndigitnumber += $lcm - $reminder; // this condition check the n digit // number is possible or not // if it is possible it return // the number else return 0 if ($ndigitnumber < pow(10, $n)) return $ndigitnumber; else return 0;}// driver code $n = 4; $x = 2; $y = 3; $z = 5; $res = findDivisible($n, $x, $y, $z); // if number is possible then // it print the number if ($res != 0) echo $res; else echo "Not possible";// This code is contributed by mits.?> |
Output
1020
Time Complexity: O(log(min(x, y, z)) + log(n)), here O(log(min(x, y, z)) for doing LCM of three numbers x,y,z and O(log(n)) for doing pow(10,n-1) so overall time complexity will be O(log(min(x, y, z)) + log(n)).
Auxiliary Space: O(1)
Method 3: Iterative approach
- Start with the smallest multiple of x that has n digits: multiple = x * (10**(n-1) // x)
- Enter a loop that checks if the current multiple is divisible by y and z: while len(str(multiple)) == n:
- If multiple is divisible by y and z, return it as the answer: if multiple % y == 0 and multiple % z == 0: return multiple
Otherwise, add x to multiple and continue the loop: multiple += x - If the loop exits without finding a valid multiple, return “Not possible”: return “Not possible”
C++
#include <iostream>#include <cmath>using namespace std;int smallest_divisible_number(int x, int y, int z, int n) { // smallest multiple of x with n digits int multiple = x * (int)(pow(10, n-1) / x); while (to_string(multiple).length() == n) { if (multiple % y == 0 && multiple % z == 0) { return multiple; } multiple += x; } return -1;}int main() { cout << smallest_divisible_number(2, 3, 5, 4) << endl; // output: 1020 cout << smallest_divisible_number(3, 5, 7, 2) << endl; // output: -1 return 0;} |
Java
public class SmallestDivisibleNumber { // This function returns the smallest multiple of x with // n digits that is divisible by y and z. static String smallestDivisibleNumber(int x, int y, int z, int n) { // smallest multiple of x with n digits int multiple = x * (int)Math.floor(Math.pow(10, n - 1) / x); while (String.valueOf(multiple).length() == n) { if (multiple % y == 0 && multiple % z == 0) { return String.valueOf(multiple); } multiple += x; } return "Not possible"; } public static void main(String[] args) { // example usage System.out.println(smallestDivisibleNumber( 2, 3, 5, 4)); // output: 1020 System.out.println(smallestDivisibleNumber( 3, 5, 7, 2)); // output: Not possible }} |
Python3
def smallest_divisible_number(x, y, z, n): # smallest multiple of x with n digits multiple = x * (10**(n-1) // x) while len(str(multiple)) == n: if multiple % y == 0 and multiple % z == 0: return multiple multiple += x return "Not possible"# example usageprint(smallest_divisible_number(2, 3, 5, 4)) # output: 1020print(smallest_divisible_number(3, 5, 7, 2)) # output: Not possible |
C#
using System;public class SmallestDivisibleNumberClass{ // This function returns the smallest multiple of x with // n digits that is divisible by y and z. static string SmallestDivisibleNumber(int x, int y, int z, int n) { // smallest multiple of x with n digits int multiple = x * (int)Math.Floor(Math.Pow(10, n - 1) / x); while (multiple.ToString().Length == n) { if (multiple % y == 0 && multiple % z == 0) { return multiple.ToString(); } multiple += x; } return "Not possible"; } public static void Main(string[] args) { // example usage Console.WriteLine(SmallestDivisibleNumber(2, 3, 5, 4)); // output: 1020 Console.WriteLine(SmallestDivisibleNumber(3, 5, 7, 2)); // output: Not possible }} |
Javascript
// JavaScript program to find the smallest multiple of x with// n digits that is divisible by y and z.// Function to find the smallest multiple of x with n digits// that is divisible by y and z.function smallestDivisibleNumber(x, y, z, n) { // smallest multiple of x with n digits let multiple = x * Math.floor(Math.pow(10, n - 1) / x); while (multiple.toString().length == n) { if (multiple % y == 0 && multiple % z == 0) { return multiple.toString(); } multiple += x; } return "Not possible";}// example usageconsole.log(smallestDivisibleNumber(2, 3, 5, 4)); // output: 1020console.log(smallestDivisibleNumber(3, 5, 7, 2)); // output: Not possible |
Output
1020 -1
The time complexity of the approach can be expressed as O(n/x).
The auxiliary space of the approach is 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!
