1281. Subtract the Product and Sum of Digits of an Integer


Problem Description

Given an integer n, the task is to find the difference between two quantities related to the digits of n. These quantities are the product of all the digits of n and the sum of all the digits of n. To clarify, if n is 234, the product of its digits is 2 * 3 * 4 which equals 24, and the sum of its digits is 2 + 3 + 4 which equals 9. The result to return for the problem would be the product minus the sum, thus 24 - 9 = 15.

Intuition

To solve this problem, we can simulate the process of extracting each digit of the number n, and then perform the respective multiplication and addition operations with these digits.

Firstly, consider the need to handle each digit of the integer n separately. A convenient way to extract the digits of an integer is by repeatedly dividing the number by 10 and taking the remainder, which gives us the last digit of the current number. In each iteration, we remove this last digit by performing integer division by 10.

With each digit extracted, we can directly calculate two running totals: one for the product of the digits, and another for the sum of the digits.

  1. We initialize a variable (let's call it x) to 1 to hold the product (since the product of zero is zero, which would nullify all subsequent multiplications).
  2. We initialize another variable (let's call it y) to 0 to hold the sum (since adding zero does not change the sum).
  3. As we extract each digit v, we update x by multiplying it with v (x = x * v) and update y by adding v to it (y = y + v).
  4. After we have finished processing all the digits of n, we calculate the difference between the product and the sum (x - y) and return this as our result.

This approach allows us to keep track of both the product and the sum of the digits of n in a single pass over the number, which is both efficient and straightforward.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The solution follows a straightforward simulation approach. The goal is to iterate through each digit of the given number n and calculate both the product and the sum of these digits. To make it possible, we employ a basic while loop that continues to execute as long as the number n is greater than 0.

Below are the steps outlining the implementation details and the logical flow of the program:

  1. We start by initializing two variables: x with a value of 1 to serve as the accumulator for the product, and y with a value of 0 to serve as the accumulator for the sum of the digits.

  2. We enter a while loop that will run until n becomes 0.

  3. Inside the loop, we utilize the divmod function, which performs both integer division and modulo operation in a single step. The statement n, v = divmod(n, 10) divides n by 10, with the quotient assigned back to n (essentially stripping off the last digit) and the remainder assigned to v (which is the last digit of the current n).

  4. With the digit v isolated, we update our product variable x by multiplying it by v (since x keeps the running product of the digits).

  5. Similarly, we update our sum variable y by adding v to it, keeping a running sum of the digits.

  6. After the loop has completed (all digits of n have been processed), the variable x holds the product of the digits, and the variable y holds the sum of the digits of the initial n.

  7. Lastly, we return the difference between these two values, x - y.

This algorithm makes use of very basic operators and control structures in Python and does not require the use of any complex data structures or patterns. The simplicity of the algorithm—iterating over each digit, maintaining running totals for the product and sum, and then returning the difference—illustrates the power of a linear implementation that performs the required operations in a single pass over the digits of the input number.

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

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's illustrate the solution approach using the integer n = 523.

  1. Initialize two variables: x as 1 (for product) and y as 0 (for sum).
  2. Begin a while loop; n is 523, which is greater than 0, so we proceed.
  3. Inside the loop, we apply divmod operation: n, v = divmod(523, 10) which gives n = 52 and v = 3.
  4. Update x by multiplying it with v: x = 1 * 3 = 3.
  5. Update y by adding v: y = 0 + 3 = 3.
  6. Loop iterates again. Now n is 52. Apply divmod: n, v = divmod(52, 10) which gives n = 5 and v = 2.
  7. Update x: x = 3 * 2 = 6.
  8. Update y: y = 3 + 2 = 5.
  9. Loop iterates again. Now n is 5. Apply divmod: n, v = divmod(5, 10) which gives n = 0 and v = 5 (we have extracted the last digit).
  10. Update x: x = 6 * 5 = 30.
  11. Update y: y = 5 + 5 = 10.
  12. Loop ends since n is now 0.
  13. We now have x = 30 and y = 10. Calculate the difference: x - y = 30 - 10 = 20.
  14. The result is 20, which is the difference between the product of 523's digits and the sum of 523's digits.

The walkthrough demonstrates the simple, yet effective, process of using a loop to tear down the number into its constituent digits, calculate the running product and sum, and finally determine the difference between these two quantities.

Not Sure What to Study? Take the 2-min Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Python Solution

1class Solution:
2  
3    def subtractProductAndSum(self, n: int) -> int:
4        # Initialize the product and sum variables
5        product_of_digits = 1  # Holds the product of the digits
6        sum_of_digits = 0      # Holds the sum of the digits
7      
8        # Loop through each digit of the number
9        while n:
10            # Divmod returns the quotient and the remainder
11            # n becomes the quotient, and digit holds the remainder (current digit)
12            n, digit = divmod(n, 10)
13          
14            # Multiply the current digit by the product
15            product_of_digits *= digit
16          
17            # Add the current digit to the sum
18            sum_of_digits += digit
19          
20        # Return the result of subtracting the sum from the product of digits
21        return product_of_digits - sum_of_digits
22

Java Solution

1class Solution {
2  
3    // Function to subtract the product of digits from the sum of digits of an integer
4    public int subtractProductAndSum(int n) {
5        // Initializing product to 1 as we will multiply digits with it
6        int product = 1;
7        // Initializing sum to 0 as we will add digits to it
8        int sum = 0;
9      
10        // Looping through each digit of the number
11        while (n > 0) {
12            // Getting the last digit of the number
13            int digit = n % 10;
14          
15            // Multiplying the current digit with the product
16            product *= digit;
17            // Adding the current digit to the sum
18            sum += digit;
19          
20            // Removing the last digit from n
21            n /= 10;
22        }
23        // Returning the difference between the product and the sum
24        return product - sum;
25    }
26}
27

C++ Solution

1class Solution {
2public:
3    int subtractProductAndSum(int n) {
4        int product = 1; // Initialize product to 1 since we are multiplying
5        int sum = 0;     // Initialize sum to 0 since we are adding
6
7        // Loop through each digit of the number
8        while (n > 0) {
9            int digit = n % 10; // Get the last digit
10            product *= digit;   // Multiply the digit to the product
11            sum += digit;       // Add the digit to the sum
12            n /= 10;            // Remove the last digit from the number
13        }
14
15        // Return the difference between the product and sum of digits
16        return product - sum;
17    }
18};
19

Typescript Solution

1// Function to calculate and return the difference between the product
2// of digits and the sum of digits of the given number.
3function subtractProductAndSum(n: number): number {
4    // Initialize product to 1 and sum to 0
5    let product = 1;
6    let sum = 0;
7
8    // Loop to process each digit in the number
9    while (n > 0) {
10        // Extract the last digit using modulo operation
11        const digit = n % 10;
12
13        // Multiply the product by the digit
14        product *= digit;
15
16        // Add the digit to the sum
17        sum += digit;
18
19        // Remove the last digit by dividing by 10 and flooring the result
20        // to get an integer for the next iteration
21        n = Math.floor(n / 10);
22    }
23
24    // Return the difference between product and sum
25    return product - sum;
26}
27
Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Time and Space Complexity

The time complexity of the given code is O(log n) where n is the input integer. This is because the while loop runs once for each digit of n, and the number of digits in n is proportional to the logarithm of n.

The space complexity of the code is O(1). This is constant space complexity because the algorithm only uses a fixed amount of additional space (variables x and y, and temporary variables for intermediate calculations like n and v) that does not scale with the input size n.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫