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.

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).
We initialize another variable (let's call it y) to 0 to hold the sum (since adding zero does not change the sum).
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).
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 algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

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:

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.
We enter a while loop that will run until n becomes 0.
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).
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).
Similarly, we update our sum variable y by adding v to it, keeping a running sum of the digits.
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.
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:

Example Walkthrough

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

Initialize two variables: x as 1 (for product) and y as 0 (for sum).
Begin a while loop; n is 523, which is greater than 0, so we proceed.
Inside the loop, we apply divmod operation: n, v = divmod(523, 10) which gives n = 52 and v = 3.
Update x by multiplying it with v: x = 1 * 3 = 3.
Update y by adding v: y = 0 + 3 = 3.
Loop iterates again. Now n is 52. Apply divmod: n, v = divmod(52, 10) which gives n = 5 and v = 2.
Update x: x = 3 * 2 = 6.
Update y: y = 3 + 2 = 5.
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).
Update x: x = 6 * 5 = 30.
Update y: y = 5 + 5 = 10.
Loop ends since n is now 0.
We now have x = 30 and y = 10. Calculate the difference: x - y = 30 - 10 = 20.
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.

Solution Implementation

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

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

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

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

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

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

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 using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

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

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings