3345. Smallest Divisible Digit Product I

EasyMathEnumeration

Problem Description

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.

Intuition

The task is to find the smallest integer greater than or equal to a given number n such that the product of its digits is divisible by a given integer t. This can be approached by iterating over each number starting from n and calculating the product of its digits. The main insight is the observation that within any sequence of 10 consecutive numbers, there will be at least one number whose digit product is zero because it will contain the digit 0. Such products when multiplied by any number will always result in zero, which is divisible by t. Hence, iterating through numbers sequentially starting from n ensures that the solution is found without missing any candidates. During the iteration, the product of digits is recalculated for each number, and we check if it is divisible by t. The first such number found is returned as the solution.

Learn more about Math patterns.

Solution Approach

To solve this problem, we employ an enumeration strategy:

Start from n: We begin our search at the given integer n. This is the smallest number that qualifies as potentially being part of the solution set.
Iterate Sequentially: Using a loop, we enumerate through each integer starting from n. This ensures that no possible candidate is missed.
Calculate Product of Digits: For each number, calculate the product of its digits. This is accomplished by iteratively extracting each digit of the number and multiplying them together.
Check Divisibility: Once the product of the digits is obtained, check if this product is divisible by t. If it is, the current number is our answer since it satisfies the problem's condition.
Return the First Valid Number: The first number that meets the divisibility condition is returned, ensuring it's the smallest possible solution.

Use the following algorithm implemented in python:

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        for i in count(n):
            p = 1
            x = i
            while x:
                p *= x % 10
                x //= 10
            if p % t == 0:
                return i

In this implementation:

The count function creates an infinite loop starting from n, checking each subsequent integer.
For each number i, by setting x = i, we extract and multiply the digits of x.
The termination condition is when p % t == 0, ensuring the product of digits of i is divisible by t, thus ensuring correctness.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution approach using a simple example:

Assume we have n = 15 and t = 5. We are tasked with finding the smallest integer greater than or equal to 15 such that the product of its digits is divisible by 5.

Start from n = 15:
- We initialize our search at 15.
Iterate Sequentially:
- We begin checking from 15, moving sequentially to 16, 17, and so forth, until we find a valid number.
Calculate Product of Digits:
- For 15, the digits are 1 and 5. So, the product is 1 * 5 = 5.
Check Divisibility:
- We check if 5 (the product of digits) is divisible by t (5). Since 5 % 5 == 0, it's divisible. Therefore, 15 is a candidate.
Return the First Valid Number:
- 15 is the first number we checked, and since it meets the criteria, it is returned as the solution.

Thus, using this step-by-step exploration, we find that 15 is the smallest integer with the desired properties.

Solution Implementation

1from itertools import count
2
3class Solution:
4    def smallestNumber(self, n: int, t: int) -> int:
5        # Iterate over integers starting from n
6        for i in count(n):
7            product_of_digits = 1
8            current_number = i
9          
10            # Calculate the product of digits of the current number
11            while current_number:
12                digit = current_number % 10
13                product_of_digits *= digit
14                current_number //= 10
15          
16            # Check if the product of digits is divisible by t
17            if product_of_digits % t == 0:
18                return i
19

1class Solution {
2    public int smallestNumber(int n, int t) {
3        for (int currentNumber = n;; ++currentNumber) { // Start from n, incrementing by 1 indefinitely
4            int productOfDigits = 1; // Initialize product of digits to 1
5            for (int x = currentNumber; x > 0; x /= 10) { // Loop through each digit of currentNumber
6                productOfDigits *= (x % 10); // Multiply the product by the current digit
7            }
8            if (productOfDigits % t == 0) { // Check if product of digits is divisible by t
9                return currentNumber; // Return currentNumber if condition is met
10            }
11        }
12    }
13}
14

1class Solution {
2public:
3    int smallestNumber(int n, int t) {
4        // Start checking from number n upwards
5        for (int i = n;; ++i) {
6            int product = 1; // Initialize product of digits
7
8            // Calculate product of digits of number i
9            for (int x = i; x > 0; x /= 10) {
10                product *= (x % 10); // Multiply the last digit to product
11            }
12
13            // Check if the product is divisible by t
14            if (product % t == 0) {
15                return i; // Return the smallest number satisfying the condition
16            }
17        }
18    }
19};
20

1function smallestNumber(n: number, t: number): number {
2    // Start searching from the number 'n'
3    for (let i = n; ; ++i) {
4        let productOfDigits = 1;
5
6        // Calculate the product of the digits of the current number 'i'
7        for (let currentNumber = i; currentNumber; currentNumber = Math.floor(currentNumber / 10)) {
8            productOfDigits *= currentNumber % 10;
9        }
10
11        // Check if the product of the digits is divisible by 't'
12        if (productOfDigits % t === 0) {
13            return i; // Return the smallest number meeting the condition
14        }
15    }
16}
17

Time and Space Complexity

The time complexity of the code is not $O(\log n)$ ; it is actually $O(k \times d)$ , where $k$ is the smallest number starting from n such that the product of its digits is divisible by t, and d is the number of digits in k. This is because for each number starting from n, it calculates the product of its digits which takes up to $d$ operations for each number. In the worst case, k could be large before finding a number where the product of digits is a multiple of t.

The space complexity is $O(1)$ because the algorithm does not require additional space that scales with input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: