Smallest n digit number divisible by given three numbers
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 z bool 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 int 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 code int 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 z def 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 z def 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 code x = 2 y = 3 z = 5 n = 4 print (smallest_n_digit_number(x, y, z, n)) # Output: 1020 |
C#
using System; class Program { // Function to check if a number is divisible by x, y, and z static bool 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 static void Main() { int x = 2; int y = 3; int z = 5; int n = 4; Console.WriteLine(SmallestNDigitNumber(x, y, z, n)); // Output: 1020 } } |
Javascript
// Function to check if a number is divisible by x, y, and z function 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 z function 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 code const x = 2; const y = 3; const z = 5; const n = 4; console.log(smallest_n_digit_number(x, y, z, n)); // Output: 1020 |
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, z 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 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 = 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 code int 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 gcd import math # LCM for x, y, z def 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 z def 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 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 : 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 function function gcd( $a , $b ) { return ( $a % $b ) ? gcd( $b , $a % $b ) : $b ; } // LCM for x, y, z function 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 z function 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. ?> |
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 usage print (smallest_divisible_number( 2 , 3 , 5 , 4 )) # output: 1020 print (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 usage console.log(smallestDivisibleNumber(2, 3, 5, 4)); // output: 1020 console.log(smallestDivisibleNumber(3, 5, 7, 2)); // output: Not possible |
1020 -1
The time complexity of the approach can be expressed as O(n/x).
The auxiliary space of the approach is O(1).