406. Check Divisibility by Digit Sum and Product

Walk the digits once, accumulating their sum and their product. The answer is simply whether n is divisible by (sum + product).

Idea

The problem gives a direct recipe: compute two quantities from the digits of n and test one divisibility. There is no search or optimization — the whole task is reading the digits once and combining them.

For each digit d of n:

• add d to a running sum, and
• multiply d into a running product.

Then check n % (sum + product) == 0.

Why the divisor is never zero

Every positive integer has at least one digit, and the leading digit is at least 1, so the digit sum is always >= 1. Even when a digit is 0 (which zeroes the product), sum + product >= 1 + 0 = 1. So the modulo is always well-defined — no division-by-zero guard is needed.

Algorithm

1. Initialize sum = 0 and product = 1.
2. For each digit d of n: sum += d, product *= d.
3. Return true if n % (sum + product) == 0, else false.

Worked example: n = 99

Divisor = sum + product = 18 + 81 = 99. Since 99 % 99 == 0, the answer is true.

Contrast n = 23: sum = 2 + 3 = 5, product = 2 * 3 = 6, divisor = 11. 23 % 11 = 1 != 0, so the answer is false.

Complexity

• Time: O(log n) — one pass over the digits of n (a number with value n has about log10(n) digits).
• Space: O(1) — only the two running accumulators.

class Solution {
    public boolean checkDivisibility(int n) {
        int digitSum = 0;
        int digitProduct = 1;
        int t = n;
        while (t > 0) {
            int d = t % 10;
            digitSum += d;
            digitProduct *= d;
            t /= 10;
        }
        return n % (digitSum + digitProduct) == 0;
    }
}