LeetCode 1281 - Subtract the Product and Sum of Digits of an Integer

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to compute a simple mathematical transformation on the digits of an integer. Given an integer n, we are required to find the product of its digits and the sum of its digits, then return the difference: product - sum. In other words, for a number like 234, the digits are 2, 3, and 4. Their product is 2 * 3 * 4 = 24, and their sum is 2 + 3 + 4 = 9. The final answer is 24 - 9 = 15.

The input n is guaranteed to be a positive integer between 1 and 100,000. This guarantees that the number has at most 5 digits, so we do not have to worry about large-scale performance or integer overflow in most modern languages. The output is a single integer representing the difference between the product and the sum of the digits.

Important edge cases include numbers with zero digits, like 101, where multiplying by zero will make the product zero, or numbers with only one digit, where the product and sum are equal, resulting in a difference of zero. The problem guarantees that n is always positive, so we do not need to handle negative numbers.

Approaches

The brute-force approach involves converting the number to a string or an array of digits, then computing the product and sum of digits separately. While this works correctly, it is slightly verbose and not necessary since we can work directly with integer arithmetic. Given the small input size, this approach is sufficient, but it is not the most elegant.

The optimal approach uses direct arithmetic manipulation of the number. We can extract each digit using modulo and integer division operations. This approach avoids converting the number to a string, is simple to implement, and is memory efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Convert number to string/array of digits, compute product and sum
Optimal	O(d)	O(1)	Use integer arithmetic to extract digits, compute product and sum on the fly

Here, d represents the number of digits in n. Since n <= 10^5, d <= 5, so the time complexity is effectively constant.

Algorithm Walkthrough

Initialize two variables, digit_product to 1 and digit_sum to 0. These will store the cumulative product and sum of digits.
While n is greater than zero, repeat the following steps:
Extract the last digit using digit = n % 10.
Multiply digit_product by digit and add digit to digit_sum.
Remove the last digit from n using integer division n = n // 10.
Once all digits have been processed, compute the difference digit_product - digit_sum.
Return the result.

Why it works: The algorithm maintains two invariants: digit_product always holds the product of all processed digits, and digit_sum holds the sum. By iterating through all digits exactly once, the difference is guaranteed to reflect the entire number.

Python Solution

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

This implementation initializes two variables for the product and sum. It then iteratively extracts the last digit using modulo, updates the product and sum, and removes the last digit using integer division. Once all digits are processed, it returns the difference.

Go Solution

func subtractProductAndSum(n int) int {
    digitProduct := 1
    digitSum := 0
    for n > 0 {
        digit := n % 10
        digitProduct *= digit
        digitSum += digit
        n /= 10
    }
    return digitProduct - digitSum
}

The Go version mirrors the Python logic closely. It uses integer division and modulo to extract digits and maintain cumulative product and sum. Go handles integer arithmetic safely for these small numbers, so no special considerations are needed.

Worked Examples

Example 1: n = 234

Step	n	digit	digit_product	digit_sum
1	234	4	1*4=4	0+4=4
2	23	3	4*3=12	4+3=7
3	2	2	12*2=24	7+2=9
Final	0	-	24	9
Result	-	-	24-9=15	-

Example 2: n = 4421

Step	n	digit	digit_product	digit_sum
1	4421	1	1*1=1	0+1=1
2	442	2	1*2=2	1+2=3
3	44	4	2*4=8	3+4=7
4	4	4	8*4=32	7+4=11
Final	0	-	32	11
Result	-	-	32-11=21	-

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Each digit is processed exactly once. `d` is the number of digits, which is ≤5.
Space	O(1)	Only two variables are used regardless of input size.

The algorithm is extremely efficient due to the small number of digits. Even the brute-force approach would be fast, but this optimal method avoids unnecessary memory allocation.

Test Cases

# Provided examples
assert Solution().subtractProductAndSum(234) == 15  # standard multi-digit number
assert Solution().subtractProductAndSum(4421) == 21  # larger number with repeated digits

# Edge cases
assert Solution().subtractProductAndSum(1) == 0  # single digit
assert Solution().subtractProductAndSum(10) == -1  # contains zero, product becomes 0
assert Solution().subtractProductAndSum(101) == -2  # zeros in middle
assert Solution().subtractProductAndSum(99999) == 59040  # maximum 5-digit number
assert Solution().subtractProductAndSum(11111) == 0  # all digits same

Test	Why
234	typical multi-digit input
4421	repeated digits, larger number
1	single digit edge case
10	contains zero
101	zeros in middle digits
99999	maximum 5-digit number
11111	all digits same

Edge Cases

One edge case is a single-digit number, like n = 1. Here, the product and sum are the same, resulting in a zero difference. The algorithm handles this correctly because it initializes digit_product to 1 and digit_sum to 0.

Another edge case is a number containing zero, such as n = 101. Multiplying by zero will set the product to zero, and the sum will still count all digits. The algorithm correctly computes 0 - (1+0+1) = -2.

A third edge case is the largest allowed number, n = 100000. Even though it has six digits, only five of them are nonzero. The algorithm scales naturally, performing exactly as expected without overflow or errors. This ensures correctness across the input constraints.