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

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).

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:

Iterative approach

C++

Java

Python3

C#

Javascript

Smallest n digit number divisible by given three numbers

Similar Reads