You are given two integers n and t. Return the smallest number greater than or equal to n such that the product of its digits is divisible by t.
Example 1:
Input: n = 10, t = 2
Output: 10
Explanation:
The digit product of 10 is 0, which is divisible by 2, making it the smallest number greater than or equal to 10 that satisfies the condition.
Example 2:
Input: n = 15, t = 3
Output: 16
Explanation:
The digit product of 16 is 6, which is divisible by 3, making it the smallest number greater than or equal to 15 that satisfies the condition.
Constraints:
1 <= n <= 1001 <= t <= 10This approach involves iterating through each number starting from n and calculating the product of its digits. If the product is divisible by t, then that number is returned as the answer. This is the straightforward solution and can be implemented efficiently given the constraints of the problem.
The function digitProduct calculates the product of the digits of a number. The main function smallestNumber iteratively checks each integer starting from n to find the smallest number whose digit product is divisible by t.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) in practice, since the maximum number of iterations is limited by the small input constraint.
Space Complexity: O(1).
This approach checks each number starting from n and terminates early when a number with digit '0' in it is found, as its digit product will be zero and divisible by any t.
This optimized C code provides an early exit if a zero digit is found, improving performance when possible.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) for the average case with early termination.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(1) in practice, since the maximum number of iterations is limited by the small input constraint. |
| Direct Check with Early Termination | Time Complexity: O(1) for the average case with early termination. |
Make Sum Divisible by P - Leetcode 1590 - Python • NeetCodeIO • 19,510 views views
Watch 9 more video solutions →Practice Smallest Divisible Digit Product I with our built-in code editor and test cases.
Practice on FleetCode