3345. Smallest Divisible Digit Product I

Problem Overview

Find the smallest integer x >= n whose digits multiply to a multiple of t.

Intuition

Find the smallest integer x >= n whose digits multiply to a multiple of t. Digit product 0 is divisible by every positive t, and every stretch of 10 consecutive integers contains a multiple of 10 (a trailing zero). So it is enough to try x = n, n+1, ..., n+9 and return the first whose digit product is divisible by t.

Algorithm

1For num from n to n + 9 inclusive:
2 Compute digitProd by repeatedly multiplying num % 10 and dividing by 10.
3 If digitProd % t == 0, return num.
4Constraints guarantee a hit inside that window.

Example Walkthrough

Input: n = 15, t = 3

1.15 -> product 1*5 = 5, 5 % 3 != 0.
2.16 -> product 1*6 = 6, 6 % 3 == 0.
3.Return 16.

Output: 16

Common Pitfalls

•Product 0 (any digit 0) satisfies the condition for every t >= 1.
•You never need to scan past n+9 - a trailing-zero number appears by then.
•n and t are tiny (n <= 100, t <= 10), so constant work is fine.
•Do not confuse digit product with digit sum.

3345.cs

// Approach: Find the smallest x >= n whose digit product is divisible by t.
// Scan x = n .. n+9. Among any 10 consecutive integers one is a multiple of
// 10 (digit product 0), so a valid answer always exists in that window.
// Complexity: O(1) time (at most 10 numbers, few digits each) and O(1) space.
public class Solution
{
    public int SmallestNumber(int n, int t)
    {
        for (int num = n; num < n + 10; ++num)
        {
            if (GetDigitProd(num) % t == 0)
                return num;
        }
        throw new ArgumentException();
    }

    private int GetDigitProd(int num)
    {
        int digitProd = 1;
        while (num > 0)
        {
            digitProd *= num % 10;
            num /= 10;
        }
        return digitProd;
    }
}

Was this solution helpful?