Problem Description

You are given a positive integer n. Your task is to determine if n is divisible by a specific sum calculated from its digits.

The sum is calculated by adding:

1. Digit sum: The sum of all individual digits in n
2. Digit product: The product of all individual digits in n

For example, if n = 234:

• Digit sum = 2 + 3 + 4 = 9
• Digit product = 2 × 3 × 4 = 24
• Total sum = 9 + 24 = 33
• Check if 234 is divisible by 33 (234 % 33 == 0)

Return true if n is divisible by (digit sum + digit product), otherwise return false.

The solution iterates through each digit of n by repeatedly using divmod to extract the last digit. It maintains two variables: s for the running digit sum and p for the running digit product (initialized to 1). After processing all digits, it checks if n % (s + p) == 0 to determine divisibility.

Intuition

The problem asks us to check divisibility based on properties derived from the digits of the number itself. To solve this, we need to extract each digit from the number and compute two values simultaneously.

The key insight is that we can extract digits from a number using the modulo and integer division operations. When we do n % 10, we get the last digit, and n // 10 removes the last digit. By repeatedly applying this process, we can visit each digit from right to left.

As we extract each digit, we can maintain running calculations for both the sum and product. We start with sum = 0 (since adding to 0 doesn't change our result) and product = 1 (since multiplying by 1 doesn't change our result). For each digit we extract, we add it to our sum and multiply it with our product.

The beauty of this approach is that we only need a single pass through the digits. We don't need to convert the number to a string or store the digits in an array - we can compute everything on the fly. Once we've processed all digits (when our number becomes 0), we have both the digit sum and digit product ready.

Finally, checking divisibility is straightforward: we use the modulo operator % to check if n % (sum + product) == 0. If the remainder is 0, then n is divisible by the sum of its digit sum and digit product.

Learn more about Math patterns.

Solution Approach

The solution uses a simulation approach to extract and process each digit of the number. Here's how the implementation works:

Step 1: Initialize Variables

• s = 0: This will store the sum of all digits
• p = 1: This will store the product of all digits (initialized to 1, not 0, since we'll be multiplying)
• x = n: Create a copy of n to work with, preserving the original value for the final divisibility check

Step 2: Extract and Process Digits The core logic uses a while loop that continues as long as x > 0:

while x:
    x, v = divmod(x, 10)
    s += v
    p *= v

The divmod(x, 10) function is particularly elegant here - it returns both the quotient and remainder in a single operation:

• The quotient (x // 10) becomes the new value of x, effectively removing the last digit
• The remainder (x % 10) is the extracted digit, stored in v

For each extracted digit v:

• Add it to the running sum: s += v
• Multiply it with the running product: p *= v

Step 3: Check Divisibility After processing all digits, check if n is divisible by the sum of digit sum and digit product:

return n % (s + p) == 0

Example Walkthrough: For n = 123:

• Initially: x = 123, s = 0, p = 1
• Iteration 1: divmod(123, 10) = (12, 3) → x = 12, v = 3, s = 3, p = 3
• Iteration 2: divmod(12, 10) = (1, 2) → x = 1, v = 2, s = 5, p = 6
• Iteration 3: divmod(1, 10) = (0, 1) → x = 0, v = 1, s = 6, p = 6
• Final check: 123 % (6 + 6) = 123 % 12 = 3 → Not divisible, return false

The time complexity is O(log n) since we process each digit once, and the number of digits is proportional to log n. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with n = 234:

Initial Setup:

• Create a copy: x = 234 (to preserve original n for final check)
• Initialize sum: s = 0
• Initialize product: p = 1

Digit Extraction Process:

Iteration 1:

• divmod(234, 10) returns (23, 4)
• Update x = 23 (removing the last digit)
• Extract digit v = 4
• Update sum: s = 0 + 4 = 4
• Update product: p = 1 × 4 = 4

Iteration 2:

• divmod(23, 10) returns (2, 3)
• Update x = 2 (removing the last digit)
• Extract digit v = 3
• Update sum: s = 4 + 3 = 7
• Update product: p = 4 × 3 = 12

Iteration 3:

• divmod(2, 10) returns (0, 2)
• Update x = 0 (removing the last digit)
• Extract digit v = 2
• Update sum: s = 7 + 2 = 9
• Update product: p = 12 × 2 = 24

Loop terminates since x = 0

Final Divisibility Check:

• Digit sum = 9
• Digit product = 24
• Total = 9 + 24 = 33
• Check: 234 % 33 = 234 ÷ 33 = 7 remainder 3
• Since remainder ≠ 0, return false

The number 234 is not divisible by 33, so the function returns false.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm iterates through each digit of the integer n. The number of digits in an integer n is ⌊log₁₀(n)⌋ + 1, which is O(log n). In each iteration, the operations performed (division, modulo, addition, multiplication) are constant time operations. Therefore, the overall time complexity is O(log n).

Space Complexity: O(1)

The algorithm uses only a fixed number of variables (s, p, x, v) regardless of the input size. These variables store intermediate values during computation but don't grow with the input. No additional data structures like arrays or recursive call stacks are used. Hence, the space complexity is constant, O(1).

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

Common Pitfalls

1. Zero Digit in the Number

The most critical pitfall occurs when the input number contains a zero digit (e.g., n = 102). When a zero is encountered, the digit product becomes 0, making the divisor (digit_sum + digit_product) potentially very small or causing unexpected behavior.

Example of the issue:

• For n = 102: digit_sum = 3, digit_product = 0
• Total = 3 + 0 = 3
• Check: 102 % 3 = 0 → Returns true

Solution: This behavior is actually correct mathematically, but you should be aware that any number with a zero digit will have a digit product of 0, significantly simplifying the divisibility check to just checking divisibility by the digit sum.

2. Division by Zero Edge Case

While not possible with positive integers and their digit operations, if the problem were extended to handle special cases or the number 0 itself, we could face division by zero.

Example of the issue:

• If somehow both digit_sum and digit_product were 0 (impossible with positive integers)
• The operation n % 0 would raise a ZeroDivisionError

Solution: Add a guard clause if extending the problem:

total = digit_sum + digit_product
if total == 0:
    return False  # or handle according to requirements
return n % total == 0

3. Integer Overflow with Large Products

For very large numbers with many non-zero digits, the digit product can grow exponentially and potentially cause integer overflow in languages with fixed-size integers.

Example of the issue:

• For n = 999999999 (nine 9s): digit_product = 9^9 = 387,420,489

Solution: In Python, this isn't an issue due to arbitrary precision integers. However, in other languages, you might need to:

• Use long/BigInteger types
• Add early termination if the product exceeds n (since n % product would be n anyway if product > n)

if digit_product > n:
    return False  # Early termination optimization

4. Incorrect Variable Initialization

A common mistake is initializing digit_product = 0 instead of digit_product = 1, which would make the product always 0 regardless of the input.

Solution: Always initialize multiplicative accumulators to 1:

digit_product = 1  # Correct
# NOT: digit_product = 0  # Wrong!