Smallest number not less than N which is divisible by all digits of N

Last Updated : 02 Jun, 2021

Given a positive integer N, the task is to find the smallest integer greater than or equal to X, having all its digits divisible by the non-zero digits of N.

Examples:

Input: N = 280
Output: 280
Explanation:
280 is the smallest which is divisible by the digits 8 and 2.

Input: N = 32
Output: 36
Explanation:
36 is the smallest number which is divisible by both the digits 2 and 3.

Approach: The idea is to find the LCM of all the non-zero digits of X and then just find the next greater multiple of that LCM value which is greater than N.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;

// Function to calculate the LCM
int LCM(int A, int B)
{
    return (A * B / __gcd(A, B));
}

// Function to find the smallest number
// satisfying given constraints
int findSmallestNumber(int X)
{
    // LCM value is 1 initially
    int lcm = 1;
    int temp = X;

    // Finding the LCM of all
    // non zero digits
    while (temp) {

        int last = temp % 10;
        temp /= 10;

        if (!last)
            continue;

        // Update the value lcm
        lcm = LCM(lcm, last);
    }

    // Stores ceil value
    int answer = ((X + lcm - 1) / lcm)
                 * lcm;

    // Print the answer
    cout << answer;
}

// Driver Code
int main()
{
    int X = 280;

    // Function Call
    findSmallestNumber(X);

    return 0;
}

Java

// Java program for the above approach
class GFG{

  // Function to calculate the LCM
  static int LCM(int A, int B)
  {
    return (A * B / __gcd(A, B));
  }

  // Function to find the smallest number
  // satisfying given constraints
  static void findSmallestNumber(int X)
  {

    // LCM value is 1 initially
    int lcm = 1;
    int temp = X;

    // Finding the LCM of all
    // non zero digits
    while (temp > 0) 
    {
      int last = temp % 10;
      temp /= 10;

      if (last == 0)
        continue;

      // Update the value lcm
      lcm = LCM(lcm, last);
    }

    // Stores ceil value
    int answer = ((X + lcm - 1) / lcm)
      * lcm;

    // Print the answer
    System.out.print(answer);

  }
  static int __gcd(int a, int b)  
  {  
    return b == 0 ? a:__gcd(b, a % b);     
  }

  // Driver Code
  public static void main(String[] args)
  {
    int X = 280;

    // Function Call
    findSmallestNumber(X);
  }
}

// This code is contributed by shikhasingrajput

Python3

# Python3 program for the above approach
import math

# Function to calculate the LCM
def LCM(A, B):
    
    return (A * B // math.gcd(A, B))

# Function to find the smallest number
# satisfying given constraints
def findSmallestNumber(X):
    
    # LCM value is 1 initially
    lcm = 1
    temp = X

    # Finding the LCM of all
    # non zero digits
    while (temp):
        last = temp % 10
        temp //= 10

        if (not last):
            continue

        # Update the value lcm
        lcm = LCM(lcm, last)

    # Stores ceil value
    answer = ((X + lcm - 1) // lcm) * lcm

    # Print the answer
    print(answer)

# Driver Code
if __name__ == "__main__":
    
    X = 280

    # Function Call
    findSmallestNumber(X)

# This code is contributed by chitranayal

// C# program for the above approach
using System;
class GFG{

  // Function to calculate the LCM
  static int LCM(int A, int B)
  {
    return (A * B / __gcd(A, B));
  }

  // Function to find the smallest number
  // satisfying given constraints
  static void findSmallestNumber(int X)
  {

    // LCM value is 1 initially
    int lcm = 1;
    int temp = X;

    // Finding the LCM of all
    // non zero digits
    while (temp > 0) 
    {
      int last = temp % 10;
      temp /= 10;

      if (last == 0)
        continue;

      // Update the value lcm
      lcm = LCM(lcm, last);
    }

    // Stores ceil value
    int answer = ((X + lcm - 1) / lcm)
      * lcm;

    // Print the answer
    Console.Write(answer);

  }
  static int __gcd(int a, int b)  
  {  
    return b == 0 ? a:__gcd(b, a % b);     
  }

  // Driver Code
  public static void Main(String[] args)
  {
    int X = 280;

    // Function Call
    findSmallestNumber(X);
  }
}

// This code is contributed by shikhasingrajput

JavaScript

<script>

// JavaScript program for the above approach

// Function to calculate the LCM
function LCM(A,B)
{
    return (A * B / __gcd(A, B));
}

// Function to find the smallest number
  // satisfying given constraints
function findSmallestNumber(X)
{
    // LCM value is 1 initially
    let lcm = 1;
    let temp = X;
 
    // Finding the LCM of all
    // non zero digits
    while (temp > 0)
    {
      let last = temp % 10;
      temp = Math.floor(temp/10);
 
      if (last == 0)
        continue;
 
      // Update the value lcm
      lcm = LCM(lcm, last);
    }
 
    // Stores ceil value
    let answer = Math.floor((X + lcm - 1) / lcm)
      * lcm;
 
    // Print the answer
    document.write(answer);
}

function __gcd(a,b)
{
    return b == 0 ? a:__gcd(b, a % b);
}

 // Driver Code
let X = 280;

// Function Call
findSmallestNumber(X);


// This code is contributed by rag2127

</script>

Output:

Time Complexity: O(N*log₁₀N)
Auxiliary Space: O(1)

Smallest even digits number not less than N

reapedjuggler

Improve

Article Tags :

Practice Tags :

Smallest number not less than N which is divisible by all digits of N

Similar Reads

Thank You!

What kind of Experience do you want to share?