Subtract the Product and Sum of Digits of an Integer
EasyPrompt
n, return the difference between the product of its digits and the sum of its digits.
Example 1:
Input: n = 234
Output: 15
Explanation:
Product of digits = 2 * 3 * 4 = 24
Sum of digits = 2 + 3 + 4 = 9
Result = 24 - 9 = 15Example 2:
Input: n = 4421
Output: 21
Explanation:
Product of digits = 4 * 4 * 2 * 1 = 32
Sum of digits = 4 + 4 + 2 + 1 = 11
Result = 32 - 11 = 21
Constraints:
1 <= n <= 10^5
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves converting the integer into a string. Once we have the string representation, we can iterate through each character, convert it back to its numeric value, and then calculate the product and sum of these digits.
Algorithm
- Convert the input integer
nto its string representation. - Initialize two variables:
sumOfDigitsto 0 andproductOfDigitsto 1. - Iterate through each character of the string.
- For each character, convert it to its integer equivalent.
- Add this integer value to
sumOfDigits. - Multiply
productOfDigitsby this integer value. - After the loop finishes, return the difference
productOfDigits - sumOfDigits.
Walkthrough
The core idea is to leverage built-in string conversion functions. We first convert the number n into a string. Then, we can easily iterate over this string. In each iteration, we get a character representing a digit, which we convert back to an integer. We maintain two running variables, one for the sum and one for the product, updating them with each digit. Finally, we compute the difference.
class Solution { public int subtractProductAndSum(int n) { String s = Integer.toString(n); int sumOfDigits = 0; int productOfDigits = 1; for (char c : s.toCharArray()) { int digit = Character.getNumericValue(c); sumOfDigits += digit; productOfDigits *= digit; } return productOfDigits - sumOfDigits; }}Complexity
Time
O(log10(n)). The time taken is proportional to the number of digits in `n`. Converting an integer to a string takes O(log10(n)) time, and iterating through the string also takes O(log10(n)) time.
Space
O(log10(n)). We need extra space to store the string representation of the number, and the length of the string is proportional to the number of digits in `n`.
Trade-offs
Pros
Conceptually simple and easy to read for those familiar with string manipulation.
Cons
Less efficient in terms of space compared to the mathematical approach due to the creation of an intermediate string.
May be slightly slower in practice due to the overhead of string conversion and character parsing.
A more efficient approach is to extract digits using mathematical operations, specifically the modulo (%) and division (/) operators. This avoids the overhead of converting the number to a string and is the optimal way to solve this problem.
Algorithm
- Initialize
sum = 0andproduct = 1. - While
n > 0:- Get the last digit:
digit = n % 10. - Update
sum = sum + digit. - Update
product = product * digit. - Remove the last digit from
n:n = n / 10.
- Get the last digit:
- Return
product - sum.
Walkthrough
This method directly manipulates the integer to extract its digits. We can get the last digit of a number by taking the number modulo 10 (i.e., n % 10). After processing the last digit, we can remove it from the number by performing integer division by 10 (i.e., n / 10). We repeat this process in a loop until the number becomes 0. Throughout the loop, we accumulate the sum and product of the digits.
class Solution { public int subtractProductAndSum(int n) { int sumOfDigits = 0; int productOfDigits = 1; while (n > 0) { int digit = n % 10; sumOfDigits += digit; productOfDigits *= digit; n /= 10; } return productOfDigits - sumOfDigits; }}Complexity
Time
O(log10(n)). The loop runs once for each digit of the number `n`. The number of digits is proportional to log base 10 of `n`.
Space
O(1). This approach uses a constant amount of extra space for variables like `sumOfDigits`, `productOfDigits`, and `digit`, regardless of the input number's size.
Trade-offs
Pros
Highly efficient in terms of both time and space.
Avoids the overhead of string conversions, making it faster in practice.
Uses constant extra space.
Cons
Might be slightly less intuitive for beginners compared to the string manipulation approach.
Solutions
Solution
public class Solution { public int SubtractProductAndSum(int n) { int x = 1; int y = 0; for (; n > 0; n /= 10) { int v = n % 10; x *= v; y += v; } return x - y; }}class Solution {public int subtractProductAndSum(int n) { int x = 1, y = 0; for (; n > 0; n /= 10) { int v = n % 10; x *= v; y += v; } return x - y; }}class Solution {public: int subtractProductAndSum(int n) { int x = 1, y = 0; for (; n; n /= 10) { int v = n % 10; x *= v; y += v; } return x - y; }};class Solution: def subtractProductAndSum(self, n: int) -> int: x, y = 1, 0 while n: n, v = divmod(n, 10) x *= v y += v return x - yVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.