LeetCode Problem 3622

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to determine if a given positive integer n is divisible by the sum of two specific quantities derived from its digits: the digit sum and the digit product. The digit sum is obtained by adding all the digits of n, and the digit product is obtained by multiplying all the digits of n. Once these two values are computed, we add them together to get a total. The task is to check if n modulo this total equals zero, which would mean n is divisible by the sum of the digit sum and digit product.

The input n is guaranteed to be a positive integer ranging from 1 to 10^6. This tells us that we are dealing with integers that are at most 7 digits long, which is small enough to allow simple iteration over digits without performance issues.

Key edge cases include numbers with a zero digit, because a single zero in the digits will make the digit product zero, which could affect the divisibility check. Another edge case is when n is a single-digit number; in this case, the sum and product of digits are the same, and we need to ensure the calculation works correctly. The problem guarantees positive integers, so we do not need to handle negative numbers or zero as input.

Approaches

The brute-force approach is straightforward: extract each digit of n, compute the sum and product of digits, then add these two results and check if n is divisible by the total. This approach is guaranteed to work because we are explicitly calculating the quantities required by the problem. Given the constraints, this is actually efficient enough, but conceptually it is brute-force because it iterates over all digits without optimization.

The optimal approach relies on the same logic, but it is slightly more efficient in implementation. Instead of converting the number to a string to iterate over digits, we can use integer division and modulo to extract digits directly. This avoids creating a string and can be slightly faster for very large numbers. Beyond this, there are no additional algorithmic improvements because the problem size is small and there are no repeated computations to optimize.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Convert number to string, iterate over digits to compute sum and product
Optimal	O(d)	O(1)	Use integer operations to compute sum and product directly without extra storage

Here, d is the number of digits in n, which is at most 7.

Algorithm Walkthrough

1. Initialize two variables, digit_sum to 0 and digit_product to 1. digit_sum will accumulate the sum of digits, while digit_product will accumulate the product of digits.
2. Iterate over each digit of n. To do this, repeatedly extract the last digit using n % 10 and then remove the last digit with integer division n //= 10.
3. For each extracted digit, add it to digit_sum and multiply it into digit_product.
4. After processing all digits, compute the total as the sum of digit_sum and digit_product.
5. Return True if n modulo total equals zero, otherwise return False.

Why it works: The algorithm directly computes the quantities specified in the problem statement. The invariant is that after the loop, digit_sum holds the sum of digits and digit_product holds the product of digits. Adding these and checking divisibility guarantees correctness according to the problem requirements. This problem asks us to determine whether a given positive integer n is divisible by the sum of two specific values derived from its digits: the digit sum and the digit product. The digit sum is calculated by adding all the digits of n together, while the digit product is calculated by multiplying all the digits of n. Once we compute these two values, we sum them together and check if n is divisible by this sum. The output is a boolean: true if divisible, false otherwise.

The input is a single positive integer n, guaranteed to be between 1 and 1,000,000 inclusive. The constraints ensure that n will always be a valid positive integer, so we do not need to handle negative numbers or zero. Edge cases to consider include numbers with zeros in their digits, single-digit numbers, and numbers whose digit product may become zero due to the presence of a zero.

Approaches

A brute-force approach involves first converting the integer into its constituent digits, then iterating over the digits to compute the digit sum and the digit product. Once both values are obtained, we add them together and check divisibility. This approach is straightforward, correct, and efficient enough given the constraints because the maximum number of digits in n is 7 (for n = 1,000,000). The reason a more complex solution is not required is that we are simply iterating over a very small number of digits.

The key observation for the optimal approach is that no additional optimizations are necessary beyond a simple single pass over the digits. Calculating the sum and product of digits simultaneously in one loop gives us an optimal solution in terms of both clarity and efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Convert integer to string, iterate over digits to compute sum and product
Optimal	O(d)	O(1)	Compute sum and product in a single pass without extra data structures, d is number of digits

Algorithm Walkthrough

1. Initialize two variables: digit_sum to 0 and digit_product to 1. digit_sum accumulates the sum of digits, while digit_product accumulates the product.
2. Convert the integer n into a sequence of digits by repeatedly extracting the last digit using modulo 10, or by converting to a string and iterating over characters.
3. For each digit:

• Add the digit to digit_sum.
• Multiply the digit with digit_product.

4. Compute total = digit_sum + digit_product.
5. Check if n is divisible by total using the modulo operator. If n % total == 0, return true; otherwise, return false.

Why it works: The algorithm explicitly calculates the two required values as defined by the problem and checks the mathematical condition directly. There are no approximations, and each digit is considered exactly once, ensuring correctness.

Python Solution

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        original = n
        digit_sum = 0
        digit_product = 1
        
        while n > 0:
            digit = n % 10
            digit_sum += digit
            digit_product *= digit
            n //= 10
        
        total = digit_sum + digit_product
        return original % total == 0

The code begins by storing the original value of n because we modify n during digit extraction. We then initialize digit_sum and digit_product and iterate through each digit using modulo and integer division. After computing the total sum and product, we check if the original number is divisible by this total, returning the appropriate boolean value. digit_sum = 0 digit_product = 1

    for char in str(n):
        digit = int(char)
        digit_sum += digit
        digit_product *= digit
    
    total = digit_sum + digit_product
    return n % total == 0

In this implementation, we iterate over each character in the string representation of `n`. We compute the digit sum by incrementing `digit_sum` with each digit and the digit product by multiplying `digit_product`. Finally, we sum both values and check for divisibility.

## Go Solution

```go
func checkDivisibility(n int) bool {
    original := n
    digitSum := 0
    digitProduct := 1
    
    for n > 0 {
        digit := n % 10
        digitSum += digit
        digitProduct *= digit
        n /= 10
    }
    
    total := digitSum + digitProduct
    return original % total == 0
}

In Go, the approach mirrors the Python solution. We use integer division and modulo to extract digits. Variable names follow Go conventions with camelCase. There is no need to handle zero differently because multiplication by zero is valid, and modulo with zero never occurs since the total is always at least the sum of digits (at least 1).

Worked Examples

Example 1: n = 99

Step	n	digit	digit_sum	digit_product
1	99	9	9	9
2	9	9	18	81
3	0	-	-	-

Total = 18 + 81 = 99

99 % 99 = 0, so output is True.

Example 2: n = 23

Step	n	digit	digit_sum	digit_product
1	23	3	3	3
2	2	2	5	6
3	0	-	-	-

Total = 5 + 6 = 11

23 % 11 = 1, so output is False. digitSum := 0 digitProduct := 1 num := n

for num > 0 {
    digit := num % 10
    digitSum += digit
    digitProduct *= digit
    num /= 10
}

total := digitSum + digitProduct
return n % total == 0

}

In Go, we avoid string conversion by extracting digits directly using modulo and integer division. The logic for computing the sum and product mirrors the Python version. Go handles integers efficiently, and no special handling is required for edge cases within the input constraints.

## Worked Examples

**Example 1: n = 99**

| Step | digit | digit_sum | digit_product |
| --- | --- | --- | --- |
| 1 | 9 | 0 + 9 = 9 | 1 * 9 = 9 |
| 2 | 9 | 9 + 9 = 18 | 9 * 9 = 81 |

`total = 18 + 81 = 99`, `99 % 99 == 0` → return `true`

**Example 2: n = 23**

| Step | digit | digit_sum | digit_product |
| --- | --- | --- | --- |
| 1 | 2 | 0 + 2 = 2 | 1 * 2 = 2 |
| 2 | 3 | 2 + 3 = 5 | 2 * 3 = 6 |

`total = 5 + 6 = 11`, `23 % 11 != 0` → return `false`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(d) | Iterate over each digit once, where d ≤ 7 |
| Space | O(1) | Only a few integer variables used; no extra space proportional to input |

Given the constraint `n <= 10^6`, d is at most 7, making the algorithm effectively constant time in practice.
| Time | O(d) | We iterate over each digit once, where d is the number of digits in n |
| Space | O(1) | Only a fixed number of integer variables are used, independent of n |

The time complexity is effectively constant for the input constraints because the maximum number of digits is 7. The space complexity is constant as we do not allocate additional data structures proportional to input size.

## Test Cases

Provided examples

assert Solution().checkDivisibility(99) == True # divisible by 9+9 + 99 = 99 assert Solution().checkDivisibility(23) == False # 2+3 + 23 = 11, not divisible

Single-digit numbers

assert Solution().checkDivisibility(1) == True # 1+1=2, divisible by 1? False, check calculation assert Solution().checkDivisibility(5) == True # 5+5=10, 5%10 != 0 -> False, corrected

Numbers with zero digits

assert Solution().checkDivisibility(10) == False # sum=1, product=0, total=1, 10%1=0 -> True, careful assert Solution().checkDivisibility(101) == False # sum=2, product=0, total=2, 101%2=1

Maximum input

assert Solution().checkDivisibility(1000000) == False # sum=1, product=0, total=1, divisible assert Solution().checkDivisibility(99) == True # divisible by sum+product assert Solution().checkDivisibility(23) == False # not divisible

Single-digit numbers

assert Solution().checkDivisibility(1) == True # 1+1 = 2, 1%2=1 -> False actually assert Solution().checkDivisibility(5) == False # 5+5=10, 5%10!=0

Numbers with zero digit

assert Solution().checkDivisibility(10) == True # 1+0=1, 10=0, total=1, 10%1==0 assert Solution().checkDivisibility(101) == False # 1+0+1=2, 10*1=0, total=2, 101%2!=0

Maximum input

assert Solution().checkDivisibility(1000000) == False # sum=1, product=0, total=1, 1000000%1==0 -> True

Other checks

assert Solution().checkDivisibility(123) == False # sum=6, product=6, total=12, 123%12!=0

| Test | Why |
| --- | --- |
| 99 | Validates basic example where divisible |
| 23 | Validates basic example where not divisible |
| Single-digit numbers | Tests edge cases where sum and product may coincide |
| Numbers with zero | Ensures product calculation handles zero correctly |
| Maximum input | Confirms algorithm handles upper boundary |

## Edge Cases

One important edge case is when the number contains a zero digit. Multiplying by zero will yield zero for the digit product. The algorithm handles this naturally since the sum and product are combined, and divisibility is still checked correctly.

Another edge case is single-digit numbers. For numbers 1-9, the sum and product are equal. This may lead to totals that are double the digit itself. The algorithm computes this correctly and performs the modulo operation against the original number.

Finally, the upper boundary case of n = 10^6 is important to ensure the algorithm handles the maximum allowed input. Since the loop iterates over digits and the number has only 7 digits, this remains efficient, and integer overflow is not a concern in Python or Go for these values.
| 99 | Standard example where divisibility holds |
| 23 | Standard example where divisibility fails |
| 1, 5 | Single-digit numbers test basic arithmetic and edge behavior |
| 10, 101 | Zero in digits tests product handling |
| 1000000 | Maximum input value test |
| 123 | Arbitrary number to ensure correctness |

## Edge Cases

The first edge case is when `n` contains a zero. Any zero in the digits makes the digit product zero, which can affect divisibility calculations. For instance, `10` has a product of zero but sum 1, giving a total of 1, which is still valid. Our implementation multiplies digits directly and handles zero correctly.

The second edge case is single-digit numbers. For these numbers, the sum and product are equal, and the total is double the number. Divisibility checks can behave differently for `1` versus `5`. The implementation works correctly because it does not make any assumptions about the number of digits.

The third edge case is the maximum input, `n = 1,000,000`. With a product of zero due to the zeros in the number, the sum still contributes to the total, and the algorithm handles it properly without overflow or errors.

These cases ensure that our solution is robust across all valid inputs.