3622: Check Divisibility by Digit Sum and Product

Problem Statement

Given a positive integer n, determine if n is divisible by the sum of its digit sum and digit product. Return true if divisible, otherwise false.

Formally: Let S = sum of digits of n, P = product of digits of n. Return true if n % (S + P) == 0.

Key Insight

The problem requires:

1. Extracting each digit from the number
2. Calculating the sum of the digits (S)
3. Calculating the product of the digits (P)
4. Checking divisibility: n % (S + P) == 0

Approach 1: Modulus Digit Extraction

Extract digits using modulus and division operations.

Algorithm Steps

1. Initialize sum = 0 and product = 1
2. Make a copy of n (to preserve original value)
3. While the number > 0:
   • Extract last digit: digit = num % 10
   • Add digit to sum
   • Multiply digit with product
   • Remove last digit: num = num / 10
4. Compute total = sum + product
5. Check if n % total == 0

Complexity Analysis

Where d is number of digits in n. Since n ≤ 10^6, d ≤ 7.

class Solution {
public:
    bool checkDivisibility(int n) {
        int num = n;
        int sum = 0;
        int product = 1;
        
        while (num > 0) {
            int digit = num % 10;
            sum += digit;
            product *= digit;
            num /= 10;
        }
        
        int total = sum + product;
        return (n % total == 0);
    }
};

class Solution {
    public boolean checkDivisibility(int n) {
        int num = n;
        int sum = 0;
        int product = 1;
        
        while (num > 0) {
            int digit = num % 10;
            sum += digit;
            product *= digit;
            num /= 10;
        }
        
        int total = sum + product;
        return (n % total == 0);
    }
}

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

Approach 2: String Conversion Method

Convert number to string and process each character.

Algorithm Steps

1. Convert integer n to string
2. Iterate through each character in the string:
   • Convert char to digit
   • Add digit to sum
   • Multiply digit with product
3. Compute total = sum + product
4. Check if n % total == 0

Complexity Analysis

Where d is number of digits. Conversion to string requires O(d) space.

class Solution {
public:
    bool checkDivisibility(int n) {
        string num_str = to_string(n);
        int sum = 0;
        int product = 1;
        
        for (char c : num_str) {
            int digit = c - '0';
            sum += digit;
            product *= digit;
        }
        
        int total = sum + product;
        return (n % total == 0);
    }
};

class Solution {
    public boolean checkDivisibility(int n) {
        String num_str = Integer.toString(n);
        int sum = 0;
        int product = 1;
        
        for (char c : num_str.toCharArray()) {
            int digit = c - '0';
            sum += digit;
            product *= digit;
        }
        
        int total = sum + product;
        return (n % total == 0);
    }
}

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        num_str = str(n)
        digit_sum = 0
        product = 1
        
        for char in num_str:
            digit = int(char)
            digit_sum += digit
            product *= digit
        
        total = digit_sum + product
        return n % total == 0

Approach 3: Functional Programming Style (Python)

Use Python's functional programming features for concise implementation.

Algorithm Steps

1. Convert number to string
2. Map each character to integer digit
3. Compute sum using sum()
4. Compute product using reduce() with multiplication
5. Check divisibility condition

Complexity Analysis

Same as string conversion method but more concise.

from functools import reduce
import operator

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        digits = [int(d) for d in str(n)]
        digit_sum = sum(digits)
        # Handle case with zero digits
        product = reduce(operator.mul, digits, 1)
        total = digit_sum + product
        return n % total == 0

Edge Cases and Testing

1. Single Digit Numbers

Input: n = 5 → Output: false
Calculation: S=5, P=5, total=10 → 5%10=5 (not 0)

2. Numbers with Zero Digits

Input: n = 100 → Output: true
Calculation: S=1+0+0=1, P=1*0*0=0, total=1 → 100%1=0

3. Numbers with One Zero Digit

Input: n = 10 → Output: true
Calculation: S=1+0=1, P=1*0=0, total=1 → 10%1=0

4. All Digits Zero

Input: n = 0 → Output: undefined (n≥1 per constraints)

5. Large Numbers

Input: n = 999999 → Output: false
Calculation: S=54, P=531441, total=531495 → 999999 % 531495 = 468504 (not 0)

Frequently Asked Questions