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 |
Output
1020
Time complexity: O(10^n), where n is the number of digits in the required number.
Auxiliary space: O(1)
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