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

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

Tags:

#divisibility #GCD-LCM #number-theory #Numbers #DSA #Mathematical #Mathematical #number-theory #Numbers

Method 2:

Brute-force

C++

Java

Python3

C#

Javascript

Smallest n digit number divisible by given three numbers

Similar Reads