Check Divisibility by Digit Sum and Product

Difficulty: Easy | Acceptance: 69.60% | Paid: No Topics: Math

Given an integer n, return true if n is divisible by the sum of its digits and also divisible by the product of its digits, or false otherwise.

• Examples
• Constraints
• String Conversion
• Mathematical Modulo

Examples

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 <= 10^5

String Conversion

Intuition Convert the integer to a string to easily iterate over each digit. This allows us to process each character, convert it back to an integer, and calculate the sum and product.

Steps

• Convert the integer n to a string.
• Initialize digit_sum to 0 and digit_prod to 1.
• Iterate through each character in the string:
  • Convert the character to an integer d.
  • Add d to digit_sum.
  • Multiply d by digit_prod.
• If digit_prod is 0, return false (to avoid division by zero).
• Check if n % digit_sum == 0 AND n % digit_prod == 0.
• Return the result of the check.

class Solution:
    def isDivisible(self, n: int) -> bool:
        s = str(n)
        digit_sum = 0
        digit_prod = 1
        for ch in s:
            d = int(ch)
            digit_sum += d
            digit_prod *= d
        
        if digit_prod == 0:
            return False
            
        return n % digit_sum == 0 and n % digit_prod == 0

Complexity

• Time: O(log n) - The number of digits in n is proportional to log₁₀(n).
• Space: O(log n) - To store the string representation of n.
• Notes: This approach is readable but uses extra space for the string.

Mathematical Modulo

Intuition Use mathematical operations to extract digits without converting the number to a string. This is more space-efficient as it operates directly on the integer.

Steps

• Initialize digit_sum to 0 and digit_prod to 1.
• Create a temporary variable temp equal to n.
• While temp is greater than 0:
  • Get the last digit using temp % 10.
  • Add the digit to digit_sum.
  • Multiply the digit by digit_prod.
  • Remove the last digit by dividing temp by 10 (integer division).
• If digit_prod is 0, return false.
• Check if n % digit_sum == 0 AND n % digit_prod == 0.
• Return the result.

class Solution:
    def isDivisible(self, n: int) -> bool:
        digit_sum = 0
        digit_prod = 1
        temp = n
        
        while temp > 0:
            d = temp % 10
            digit_sum += d
            digit_prod *= d
            temp //= 10
            
        if digit_prod == 0:
            return False
            
        return n % digit_sum == 0 and n % digit_prod == 0

Complexity

• Time: O(log n) - We process each digit once.
• Space: O(1) - We only use a few integer variables for storage.
• Notes: This is the optimal approach for space complexity.