Smallest number greater than or equal to N which is divisible by its non-zero digits

0 0 5 minutes read

Given an integer N, the task is to find the smallest number greater than or equal to N such that it is divisible by all of its non-zero digits.

Examples:

Input: N = 31
Output: 33
Explanation: 33 is the smallest number satisfying the given condition.
At Unit’s place: 33%3 = 0
At One’s place: 33%3 = 0

Input: N = 30
Output: 30
Explanation: 30 is the smallest number satisfying the given condition.
At One’s place: 30%3 = 0

Approach: Smallest number which is divisible by all digits from 1 to 9 is equal to the LCM of (1, 2, 3, 4, 5, 6, 7, 8, 9) = 2520. Therefore, the multiples of 2520 are also divisible by all digits from 1 to 9 implying that (N + 2520) will always satisfy the condition. Therefore, iterate in the range [N, 2520 + N] and check for the smallest number satisfying the given condition. Follow the steps below to solve the problem:

Initialize ans as 0 to store the smallest number greater than or equal to N such that it is divisible by all its non-zero digits.
Iterate over the range [N, N + 2520] using the variable i.
- Initialize a variable possible as 1 to check if the current number i satisfies the given condition or not.
- Get all non-zero digits of i and check if i is divisible by each of them. If found to be true, then update possible to 1, and update ans as i, and break out of the loop.
After the above steps, print the value of ans as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
void findSmallestNumber(int n)
{
 
    // Iterate in range[N, N + 2520]
    for (int i = n; i <= (n + 2520); ++i) {
 
        // To check if the current number
        // satisfies the given condition
        bool possible = 1;
 
        // Store the number in a temporary
        // variable
        int temp = i;
 
        // Loop until temp > 0
        while (temp) {
 
            // Check only for non zero digits
            if (temp % 10 != 0) {
 
                // Extract the current digit
                int digit = temp % 10;
 
                // If number is divisible
                // by current digit or not
                if (i % digit != 0) {
 
                    // Otherwise, set
                    // possible to 0
                    possible = 0;
 
                    // Break out of the loop
                    break;
                }
            }
 
            // Divide by 10
            temp /= 10;
        }
 
        if (possible == 1) {
            cout << i;
            return;
        }
    }
}
 
// Driver Code
int main()
{
    int N = 31;
 
    // Function Call
    findSmallestNumber(N);
 
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
  
class GFG{
      
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
static void findSmallestNumber(int n)
{
     
    // Iterate in range[N, N + 2520]
    for(int i = n; i <= (n + 2520); ++i) 
    {
         
        // To check if the current number
        // satisfies the given condition
        int possible = 1;
  
        // Store the number in a temporary
        // variable
        int temp = i;
  
        // Loop until temp > 0
        while (temp != 0) 
        {
             
            // Check only for non zero digits
            if (temp % 10 != 0)
            {
                 
                // Extract the current digit
                int digit = temp % 10;
  
                // If number is divisible
                // by current digit or not
                if (i % digit != 0) 
                {
                     
                    // Otherwise, set
                    // possible to 0
                    possible = 0;
  
                    // Break out of the loop
                    break;
                }
            }
  
            // Divide by 10
            temp /= 10;
        }
  
        if (possible == 1) 
        {
            System.out.println(i);
            return;
        }
    }
}
  
// Driver code
public static void main(String[] args)
{
    int N = 31;
  
    // Function Call
    findSmallestNumber(N);
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach
 
# Function to find the smallest number
# greater than or equal to N such that
# it is divisible by its non-zero digits
def findSmallestNumber(n):
 
    # Iterate in range[N, N + 2520]
    for i in range(n, n + 2521):
 
        # To check if the current number
        # satisfies the given condition
        possible = 1
 
        # Store the number in a temporary
        # variable
        temp = i
 
        # Loop until temp > 0
        while (temp):
 
            # Check only for non zero digits
            if (temp % 10 != 0):
 
                # Extract the current digit
                digit = temp % 10
 
                # If number is divisible
                # by current digit or not
                if (i % digit != 0):
 
                    # Otherwise, set
                    # possible to 0
                    possible = 0
 
                    # Break out of the loop
                    break
 
            # Divide by 10
            temp //= 10
 
        if (possible == 1):
            print(i, end = "")
            return
 
# Driver Code
if __name__ == "__main__" :
 
    N = 31
 
    # Function Call
    findSmallestNumber(N)
     
# This code is contributed by AnkThon

C#

// C# program for the above approach 
using System;
 
class GFG{
     
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
static void findSmallestNumber(int n)
{
     
    // Iterate in range[N, N + 2520]
    for(int i = n; i <= (n + 2520); ++i) 
    {
         
        // To check if the current number
        // satisfies the given condition
        int possible = 1;
 
        // Store the number in a temporary
        // variable
        int temp = i;
 
        // Loop until temp > 0
        while (temp != 0) 
        {
             
            // Check only for non zero digits
            if (temp % 10 != 0)
            {
                 
                // Extract the current digit
                int digit = temp % 10;
 
                // If number is divisible
                // by current digit or not
                if (i % digit != 0) 
                {
                     
                    // Otherwise, set
                    // possible to 0
                    possible = 0;
 
                    // Break out of the loop
                    break;
                }
            }
 
            // Divide by 10
            temp /= 10;
        }
 
        if (possible == 1) 
        {
            Console.Write(i);
            return;
        }
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 31;
 
    // Function Call
    findSmallestNumber(N);
}
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// javascript program for the above approach 
 
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
function findSmallestNumber(n)
{
     
    // Iterate in range[N, N + 2520]
    for(i = n; i <= (n + 2520); ++i) 
    {
         
        // To check if the current number
        // satisfies the given condition
        var possible = 1;
  
        // Store the number in a temporary
        // variable
        var temp = i;
  
        // Loop until temp > 0
        while (temp != 0) 
        {
             
            // Check only for non zero digits
            if (temp % 10 != 0)
            {
                 
                // Extract the current digit
                var digit = temp % 10;
  
                // If number is divisible
                // by current digit or not
                if (i % digit != 0) 
                {
                     
                    // Otherwise, set
                    // possible to 0
                    possible = 0;
  
                    // Break out of the loop
                    break;
                }
            }
  
            // Divide by 10
            temp  = parseInt(temp / 10);
        }
  
        if (possible == 1) 
        {
            document.write(i);
            return;
        }
    }
}
  
// Driver code
var N = 31;
 
// Function Call
findSmallestNumber(N);
 
// This code is contributed by shikhasingrajput 
</script>

Output:

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

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!