3622. Check Divisibility by Digit Sum and Product

EasyMath

Leetcode Link

Problem 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.

For example, if n = 123:

The digit sum is 1 + 2 + 3 = 6.
The digit product is 1 * 2 * 3 = 6.
Their sum is 6 + 6 = 12.

Since 123 % 12 is not 0, you should return false.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, notice that we are just asked to check if n can be evenly divided by the sum of the digit sum and the digit product. The most straightforward way to find the digit sum and digit product is to go through each digit of n. For each digit, we can add it to our running sum and multiply it to our running product. Once we finish processing all digits, just add the sum and the product, and check if n is divisible by this result. The process is a simple simulation that directly follows what the problem asks.

Solution Approach

We use a simple simulation method to solve the problem. The approach involves the following steps:

Initialize two variables, s for the digit sum (starting at 0) and p for the digit product (starting at 1).
Use a loop to extract each digit from n. We do this by repeatedly taking n % 10 to get the last digit and dividing n by 10 to move to the next digit.
For each digit:
- Add the digit to s.
- Multiply the digit to p.
After processing all digits, add s and p to get the required sum.
Check if the original number n is divisible by (s + p) using the modulus operator: n % (s + p) == 0.

This approach efficiently calculates what is required in a single pass over the digits, using only basic arithmetic. No complex data structures or algorithms are needed.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution using n = 14:

Start with s = 0 (digit sum) and p = 1 (digit product).
Process each digit:
- The last digit: 14 % 10 = 4
  - Add to sum: s = 0 + 4 = 4
  - Multiply to product: p = 1 * 4 = 4
  - Update n: 14 // 10 = 1
- Next digit: 1 % 10 = 1
  - Add to sum: s = 4 + 1 = 5
  - Multiply to product: p = 4 * 1 = 4
  - Update n: 1 // 10 = 0
Now all digits have been processed. The digit sum is 5, the digit product is 4. Their sum: 5 + 4 = 9.
Check divisibility: 14 % 9 = 5, which is not 0.

Result: The function returns false for n = 14.

Solution Implementation

1class Solution:
2    def checkDivisibility(self, n: int) -> bool:
3        # Initialize variables: s for sum of digits, p for product of digits
4        s = 0  # Sum of digits
5        p = 1  # Product of digits
6        x = n  # Temporary variable to extract digits
7
8        while x:
9            x, digit = divmod(x, 10)  # Extract last digit, update x
10            s += digit               # Update sum
11            p *= digit               # Update product
12
13        # Return True if n is divisible by (sum + product) of its digits
14        return n % (s + p) == 0
15

1class Solution {
2    // Checks if the number n is divisible by the sum of the sum and product of its digits
3    public boolean checkDivisibility(int n) {
4        int digitSum = 0;      // To store the sum of digits
5        int digitProduct = 1;  // To store the product of digits
6        int num = n;           // Create a copy of n for digit extraction
7
8        // Extract digits one by one
9        while (num != 0) {
10            int digit = num % 10;   // Get the last digit
11            num /= 10;              // Remove the last digit
12            digitSum += digit;      // Add digit to sum
13            digitProduct *= digit;  // Multiply digit to product
14        }
15
16        // Check if n is divisible by the sum of digitSum and digitProduct
17        return n % (digitSum + digitProduct) == 0;
18    }
19}
20

1class Solution {
2public:
3    // This method checks if n is divisible by the sum of its digits plus their product
4    bool checkDivisibility(int n) {
5        int sum = 0;     // To accumulate the sum of the digits
6        int prod = 1;    // To accumulate the product of the digits
7        int temp = n;    // Temporary variable to process digits
8
9        while (temp != 0) {
10            int digit = temp % 10;  // Extract the last digit
11            temp /= 10;             // Remove the last digit
12
13            sum += digit;           // Add digit to sum
14            prod *= digit;          // Multiply digit to product
15        }
16
17        // Return true if n is divisible by the sum and product of its digits
18        return n % (sum + prod) == 0;
19    }
20};
21

1/**
2 * Checks if the given number is divisible by the sum of its digits and the product of its digits.
3 * @param n The number to check.
4 * @returns True if n is divisible by (sum of digits + product of digits), otherwise false.
5 */
6function checkDivisibility(n: number): boolean {
7    // Initialize sum and product of digits
8    let sum = 0;
9    let product = 1;
10    let temp = n;
11
12    // Extract digits and calculate sum and product
13    while (temp !== 0) {
14        const digit = temp % 10;
15        temp = Math.floor(temp / 10);
16        sum += digit;
17        product *= digit;
18    }
19
20    // Check divisibility
21    return n % (sum + product) === 0;
22}
23

Time and Space Complexity

The time complexity of the code is O(\log n), where n is the input integer. This is because the while loop iterates once for each digit of n, and the number of digits in n is proportional to \log_{10} n.

The space complexity is O(1), as only a fixed number of variables (s, p, x, v) are used regardless of the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know