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 = 0Input: 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 digitsvoid 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 Codeint 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 digitsstatic 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 codepublic 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 digitsdef 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 Codeif __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 digitsstatic 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 codepublic 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 digitsfunction 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 codevar N = 31;// Function CallfindSmallestNumber(N);// This code is contributed by shikhasingrajput </script> |
Output:
33
Time Complexity: O(2520*log10N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
