Skip to content

3622. Check Divisibility by Digit Sum and Product

SourceWeekly Contest 459 Q1DifficultyEasyRating1148

Description

You are given a positive integer n. Determine whether n is divisible by the sum of the following two values:

  • The digit sum of n (the sum of its digits).

  • The digit product of n (the product of its digits).

Return true if n is divisible by this sum; otherwise, return false.

 

Example 1:

Input: n = 99

Output: true

Explanation:

Since 99 is divisible by the sum (9 + 9 = 18) plus product (9 * 9 = 81) of its digits (total 99), the output is true.

Example 2:

Input: n = 23

Output: false

Explanation:

Since 23 is not divisible by the sum (2 + 3 = 5) plus product (2 * 3 = 6) of its digits (total 11), the output is false.

 

Constraints:

  • 1 <= n <= 106

Solutions

Solution 1: Simulation

Thinking

For \(n\le 10^6\) it suffices to peel digits and form their sum and product. \(\textit{divmod}\) extracts low-order digits without converting to a string.

The product starts at \(1\), not \(0\). Test whether \(s+p\) divides \(n\). There are \(O(\log n)\) digits.

We can iterate through each digit of the integer \(n\), calculating the digit sum \(s\) and digit product \(p\). Finally, we check whether \(n\) is divisible by \(s + p\).

The time complexity is \(O(\log n)\), where \(n\) is the value of the integer \(n\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def checkDivisibility(self, n: int) -> bool:
        s, p = 0, 1
        x = n
        while x:
            x, v = divmod(x, 10)
            s += v
            p *= v
        return n % (s + p) == 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public boolean checkDivisibility(int n) {
        int s = 0, p = 1;
        int x = n;
        while (x != 0) {
            int v = x % 10;
            x /= 10;
            s += v;
            p *= v;
        }
        return n % (s + p) == 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    bool checkDivisibility(int n) {
        int s = 0, p = 1;
        int x = n;
        while (x != 0) {
            int v = x % 10;
            x /= 10;
            s += v;
            p *= v;
        }
        return n % (s + p) == 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func checkDivisibility(n int) bool {
    s, p := 0, 1
    x := n
    for x != 0 {
        v := x % 10
        x /= 10
        s += v
        p *= v
    }
    return n%(s+p) == 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function checkDivisibility(n: number): boolean {
    let [s, p] = [0, 1];
    let x = n;
    while (x !== 0) {
        const v = x % 10;
        x = Math.floor(x / 10);
        s += v;
        p *= v;
    }
    return n % (s + p) === 0;
}

Comments