2160. Minimum Sum of Four Digit Number After Splitting Digits

Problem Description

In this problem, we are given a four-digit positive integer num. Our task is to split this integer into exactly two new integers, new1 and new2. To create these two new integers, we have to distribute the digits of num between them. Some important points to note about this task are:

A digit can be placed in new1 or new2 without restriction, except that all digits from num must be used.
Leading zeros are allowed in new1 and new2.
We want to minimize the sum of new1 and new2.

As an example, consider num = 2932. We can create several pairs from these digits, such as [22, 93], [23, 92], [223, 9], and [2, 329]. However, our goal is to find the pair where the sum of new1 and new2 is the smallest. This requires a strategic approach to pairing the digits into two numbers where their combined value is minimized.

Intuition

The intuition behind solving this problem lies in understanding that to minimize the sum of two numbers created from the digits of num, we need to consider digit positions carefully. The smallest sum is obtained when the least significant digits (the ones and tens place) are as small as possible in both new numbers.

One effective strategy is to:

Sort the digits of the original number in ascending order so that the smallest digits are placed in positions that contribute the least to the sum.
Assign digits to new1 and new2 strategically to ensure that the least significant digits of both numbers are as small as possible. This is because adding a smaller digit in the tens place will reduce the sum more significantly than adding it in the ones place due to the positional value in decimal notation.

Here's how we can do it:

After sorting the digits, the smallest digits will be at the front of the array. Manage these small digits so that they contribute to tens place of both the numbers.
Specifically, we take the two smallest digits and place them into the tens places of new1 and new2. This is done by multiplying the sum of these two smallest digits by 10.
Then we add the remaining two digits to the ones places.

Thus, the approach to arriving at the solution relies on sorting the four digits and then constructing two new numbers such that their sum is minimized by careful placement of the least significant digits.

Learn more about Greedy, Math and Sorting patterns.

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

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimumsAdd a heap to store the minimumsAdd a variable to track the minimumAdd a queue to store the minumums

I don’t know

Solution Approach

The solution is implemented in Python and uses fundamental programming constructs such as a list and sorting algorithm. Below is the step-by-step approach taken in the provided code:

First, we initialize an empty list, nums, which will hold the individual digits of the given num.
We then extract each digit from num using a while loop that continues until num becomes zero. We use the modulus operator % to get the least significant digit and append it to the list nums. Then, we use floor division // by 10 to remove the least significant digit from num.
```
1while num:
2    nums.append(num % 10)
3    num //= 10
```
The resulting nums list contains the individual digits in reverse order. We sort this list to arrange the digits in ascending order. Sorting is crucial to place the smallest digits in the tens places of new1 and new2 to minimize the sum.
The sorted nums list now has the smallest digit at index 0 and the second smallest at index 1. By adding the smallest two digits and multiplying by 10, we achieve two numbers with the smallest digits in the tens place:
```
1return 10 * (nums[0] + nums[1]) + nums[2] + nums[3]
```
To complete the numbers new1 and new2, we add the third smallest digit (nums[2]) and the largest digit (nums[3]) to the sum (which will occupy the ones places).
The final result returned is the minimum possible sum of new1 and new2 constructed from the digits of the original number, num.

The algorithm used is simple yet effective because it directly leverages the property of positional notation in decimal numbers. The choice of the list as the data structure enables easy manipulation of digits and the use of Python's built-in sort method streamlines digit organization.

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

Example Walkthrough

Let's walk through the solution approach with a small example. Suppose the given number is num = 4723.

Following the approach described, we perform these steps:

We start by initializing an empty list to store the digits. We call this list nums.

We then extract each digit from num and append it to nums. Processing the number 4723 gives us:

1nums = [3, 2, 7, 4]  # Note that digits are appended in reverse order

Next, we sort the nums list in ascending order:

1nums.sort()  # After sorting, nums = [2, 3, 4, 7]

Once the list is sorted, we identify the two smallest digits, which now are at indices 0 and 1. In our case, they are 2 and 3. According to our strategy, they will go into the tens places of new1 and new2. So, by adding them together and multiplying by 10, we obtain the tens place for both:
```
1Tens place sum = 10 * (2 + 3) = 50
```
Now, we take the remaining digits, which are 4 and 7, to fill in the ones places. Adding them to our tens place sum will give us the final value:
```
1Total sum = 50 + 4 + 7 = 61
```
Therefore, the smallest possible summed pair of numbers created from 4723 is $new1 = 23 and $new2 = 47, with a sum of 61.

This example demonstrates that by sorting the digits first and then strategically placing the smaller digits in the more significant tens positions across new1 and new2, we achieve the minimum sum as per the problem's requirement.

Solution Implementation

1class Solution:
2    def minimumSum(self, num: int) -> int:
3        # Initialize a list to store the digits of the input number.
4        digits = []
5      
6        # Extract the digits from the input number and append them to the list.
7        while num:
8            # Get the last digit of the number and append it to the digits list.
9            digits.append(num % 10)
10            # Remove the last digit from the number by integer division by 10.
11            num //= 10
12      
13        # Sort the digits in ascending order.
14        digits.sort()
15      
16        # Generate the minimum sum by combining the digits.
17        # The minimal sum is obtained by adding the two smallest digits after
18        # placing them in the tens place of two separate numbers, then adding
19        # the two larger digits in the units place.
20        min_sum = 10 * (digits[0] + digits[1]) + digits[2] + digits[3]
21      
22        # Return the calculated minimum sum.
23        return min_sum
24

1import java.util.Arrays; // Import Arrays class for the sort method
2
3class Solution {
4    public int minimumSum(int num) {
5        // Initialize an array to store the individual digits of the number
6        int[] digits = new int[4];
7      
8        // Extract the digits from the number and store them in the array
9        for (int i = 0; num != 0; ++i) {
10            digits[i] = num % 10; // Get the last digit of the number
11            num /= 10; // Remove the last digit from the number
12        }
13      
14        // Sort the array of digits in ascending order
15        Arrays.sort(digits);
16      
17        // Reconstruct the two minimum possible numbers by pairing the smallest digits
18        // with the next smallest digits (10s place and 1s place respectively)
19        return 10 * (digits[0] + digits[1]) + digits[2] + digits[3];
20    }
21}
22

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find the minimum sum of two numbers formed from digits of the input.
7    int minimumSum(int num) {
8        // Create a vector to store individual digits of the number
9        std::vector<int> digits;
10      
11        // Extract the digits and put them into the vector
12        while (num) {
13            digits.push_back(num % 10); // Get the last digit of 'num'
14            num /= 10;                  // Remove the last digit from 'num'
15        }
16      
17        // Sort the digits
18        std::sort(digits.begin(), digits.end());
19      
20        // The smallest two-digit numbers are formed by taking the two smallest digits
21        // and two largest digits and arranging them as shown below:
22        // For example, digits = {1, 2, 3, 5} forms 12 and 35 which is the minimum sum possible
23        return 10 * (digits[0] + digits[1]) + digits[2] + digits[3];
24    }
25};
26

1/**
2 * Calculate the minimum sum of two numbers formed from digits of the input number.
3 *
4 * @param num - A four-digit number.
5 * @returns The minimum sum of two new numbers formed by rearranging the digits.
6 */
7function minimumSum(num: number): number {
8    // Create an array to hold the individual digits of the input number
9    const digits: number[] = new Array(4).fill(0);
10
11    // Extract the digits from the input number and fill the digits array
12    for (let i = 0; i < 4; i++) {
13        digits[i] = num % 10; // Get the last digit of the current num
14        num = Math.floor(num / 10); // Remove the last digit from num
15    }
16
17    // Sort the array of digits in ascending order
18    digits.sort((a, b) => a - b);
19
20    // Form two new numbers:
21    // The first new number is formed by adding the two smallest digits, then multiplying by 10
22    // The second new number is formed from the remaining two digits
23    // This ensures the smallest possible sum
24    const newNumber1 = 10 * (digits[0] + digits[1]);
25    const newNumber2 = digits[2] + digits[3];
26
27    // Return the sum of the two new numbers
28    return newNumber1 + newNumber2;
29}
30

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

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Time and Space Complexity

Time Complexity:

The provided function consists of a while loop that iterates through the digits of the input number (num). This loop will run a number of times equal to the number of digits in num. For a 32-bit integer, the maximum number of digits is 10 (2147483647 is the largest 32-bit integer). Therefore, the while loop has a constant runtime with respect to the size of the input and does not depend on the value of num. Sorting the nums list which contains at most 4 digits using a basic sorting algorithm (like Timsort, which is used by Python's sort() method) has a constant time complexity because the number of digits is fixed and small. The final return statement is a constant time operation. Hence, overall, the time complexity is O(1), a constant time complexity.

Space Complexity:

Space is allocated for the nums list which will always have at most 4 elements since the maximum number of digits for an integer is 4 in this problem context. Hence, the space complexity of the code is O(1), a constant space complexity, since it does not grow with the size of the input number.

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

Fast Track Your Learning with Our Quick Skills Quiz:

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

2160. Minimum Sum of Four Digit Number After Splitting Digits

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity:

Space Complexity:

Recommended Readings