Minimum Sum of Four Digit Number After Splitting Digits solution and explanation
9 more videos on this problem
2160 Minimum Sum of Four Digit Number After Splitting Digits || LeetCode 2160|| Biweekly LeetCode 71Bro Coders · 6:36 · 5K views
Minimum Sum of Four Digit Number After Splitting Digits | LeetCode Biweekly Challenge 71Code Era · 5:43 · 1K views
Minimum Sum of Four Digit Number After Splitting Digits - Leetcode 2160 - PythonStreet Coder · 6:59 · 1K views
LEETCODE SOLUTION 2160 | Minimum Sum of Four Digit Number After Splitting Digits| EASY | JavascriptCodingForBeginners · 10:55 · 732 views
2160. Minimum Sum of Four Digit Number After Splitting Digits (Leetcode Easy)Programming Live with Larry · 6:19 · 685 views
Minimum Sum of Four Digit Number After Splitting Digits - LeetCode 2160 - Java Solutionalgobest - Computer Science · 4:04 · 647 views
2160 Minimum Sum of Four Digit Number After Splitting Digits | JavaScript | LeetCode SolutionArsalan Ahmed · 9:42 · 501 views
Leetcode 2160 Minimum Sum of Four Digit Number After Splitting DigitsMath Geeks · 2:39 · 334 views
Solving LeetCode problem 2160 in APL (Minimum Sum of Four Digit Number After Splitting Digits)Rodrigo's APL Corner · 5:55 · 179 views
Minimum Sum of Four Digit Number After Splitting Digits|Leetcode 2160|Approach+Code with explanationPirai's Academy · 10:05 · 114 views
The problem
You are given a positive integer num consisting of exactly four digits. Split num into two new integers new1 and new2 by using the digits found in num. Leading zeros are allowed in new1 and new2, and all the digits found in num must be used.
- For example, given
num = 2932, you have the following digits: two2's, one9and one3. Some of the possible pairs[new1, new2]are[22, 93],[23, 92],[223, 9]and[2, 329].
Return the minimum possible sum of new1 and new2.
Example 1:
Input: num = 2932 Output: 52 Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc. The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52.
Example 2:
Input: num = 4009 Output: 13 Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc. The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.
Constraints:
1000 <= num <= 9999
Approach overview
Problem Overview: You are given a four-digit integer num. Split its digits into two new integers such that every digit is used exactly once and the sum of the two numbers is minimized. The order of digits inside each number matters, so placing smaller digits in higher place values reduces the total sum.
Approach 1: Brute Force Combination (O(1) time, O(1) space)
Extract the four digits and generate every possible way to distribute them into two two-digit numbers. For each arrangement, build numbers like 10*a + b and 10*c + d, then compute the total sum. Track the minimum across all permutations. Because there are only four digits, the total permutations are constant (4! possibilities). This approach is straightforward and demonstrates the full search space, but it does unnecessary work compared to the greedy observation.
Approach 2: Sorting and Minimal Pairing (O(d log d) time, O(1) space)
Extract the digits and sort them in ascending order using a sorting algorithm. The key greedy insight: to minimize the final sum, distribute the smallest digits across the highest place values of the two numbers. After sorting d0 ≤ d1 ≤ d2 ≤ d3, construct the numbers as (10*d0 + d2) and (10*d1 + d3). This balances the digits between the tens positions instead of stacking the smallest digits in the same number. The method follows a classic greedy strategy where locally optimal placement (smallest digits in highest weight positions) leads to the globally minimal sum.
Digit extraction itself is simple arithmetic using modulo and division, a common pattern in math-based problems. After sorting, constructing the two numbers and returning their sum is constant work.
Recommended for interviews: Sorting and minimal pairing. Interviewers expect you to notice that smaller digits should occupy the tens positions of both numbers. Brute force proves correctness but the greedy approach demonstrates stronger algorithmic intuition and cleaner implementation.
Approach 1: Sorting and Minimal Pairing
To achieve the minimum sum, sort the digits of the number. This allows us to pair smaller digits together, minimizing the individual numbers formed. By arranging the sorted digits into two numbers with minimal values, we can achieve the smallest sum possible.
For instance, for num = 2932, sorting results in [2, 2, 3, 9]. If we distribute them into [2, 3] and [2, 9], we achieve 23 + 29 = 52, which is the minimum sum.
def minimum_sum(num):
digits = sorted(str(num))
new1 = int(digits[0] + digits[2])
new2 = int(digits[1] + digits[3])
return new1 + new2
num = 2932
print(minimum_sum(num))import java.util.Arrays;
public class Solution {
public static int minimumSum(int num) {
char[] digits = String.valueOf(num).toCharArray();
Arrays.sort(digits);
int new1 = (digits[0] - '0') * 10 + (digits[2] - '0');
int new2 = (digits[1] - '0') * 10 + (digits[3] - '0');
return new1 + new2;
}
public static void main(String[] args) {
int num = 2932;
System.out.println(minimumSum(num));
}
}#include <iostream>
#include <algorithm>
int minimumSum(int num) {
std::string digits = std::to_string(num);
std::sort(digits.begin(), digits.end());
int new1 = (digits[0] - '0') * 10 + (digits[2] - '0');
int new2 = (digits[1] - '0') * 10 + (digits[3] - '0');
return new1 + new2;
}
int main() {
int num = 2932;
std::cout << minimumSum(num) << std::endl;
return 0;
}function minimumSum(num) {
const digits = num.toString().split('').sort();
const new1 = parseInt(digits[0] + digits[2], 10);
const new2 = parseInt(digits[1] + digits[3], 10);
return new1 + new2;
}
const num = 2932;
console.log(minimumSum(num));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(char*)a - *(char*)b);
}
int minimumSum(int num) {
char digits[5];
snprintf(digits, 5, "%d", num);
qsort(digits, 4, sizeof(char), compare);
// Form two numbers new1 and new2
int new1 = (digits[0] - '0') * 10 + (digits[2] - '0');
int new2 = (digits[1] - '0') * 10 + (digits[3] - '0');
return new1 + new2;
}
int main() {
int num = 2932;
printf("%d\n", minimumSum(num));
return 0;
}using System;
public class Solution {
public static int MinimumSum(int num) {
char[] digits = num.ToString().ToCharArray();
Array.Sort(digits);
int new1 = (digits[0] - '0') * 10 + (digits[2] - '0');
int new2 = (digits[1] - '0') * 10 + (digits[3] - '0');
return new1 + new2;
}
public static void Main() {
int num = 2932;
Console.WriteLine(MinimumSum(num));
}
}In Python, we convert the number to a string, sort it, and then concatenate and convert pairs of characters back to integers to form the smallest possible new1 and new2, and return their sum.
Time Complexity: O(1), due to constant operations on four digits.
Space Complexity: O(1), only requires storage for a few variables.
Approach 2: Brute Force Combination
Another approach would be to consider all possible ways to distribute the four digits into two numbers new1 and new2 and calculate their sums. Then select the minimum sum. This method explores all possible combinations.
However, this method is less efficient than sorting because evaluating and summing each combination results in more operations. Sorting ensures better performance and simplicity for this specific problem.
from itertools import permutations
def minimum_sum(num):
digits = [int(d) for d in str(num)]
min_sum = float('inf')
for perm in permutations(digits):
sum1 = 10 * perm[0] + perm[1]
sum2 = 10 * perm[2] + perm[3]
min_sum = min(min_sum, sum1 + sum2)
return min_sum
num = 2932
print(minimum_sum(num))import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public static int minimumSum(int num) {
ArrayList<Integer> digits = new ArrayList<>();
digits.add(num / 1000 % 10);
digits.add(num / 100 % 10);
digits.add(num / 10 % 10);
digits.add(num % 10);
int minSum = Integer.MAX_VALUE;
Collections.sort(digits);
do {
int sum = 10 * digits.get(0) + digits.get(1) + 10 * digits.get(2) + digits.get(3);
minSum = Math.min(minSum, sum);
} while (Collections.nextPermutation(digits)); // Hypothetical utility for permutations
return minSum;
}
public static void main(String[] args) {
int num = 2932;
System.out.println(minimumSum(num));
}
}#include <iostream>
#include <algorithm>
int computeSum(int a, int b, int c, int d) {
int new1 = a * 10 + b;
int new2 = c * 10 + d;
return new1 + new2;
}
int minimumSum(int num) {
int digits[4] = {(num / 1000) % 10, (num / 100) % 10, (num / 10) % 10, num % 10};
int minSum = 10000;
std::sort(digits, digits + 4);
do {
int sum = computeSum(digits[0], digits[1], digits[2], digits[3]);
if (sum < minSum) {
minSum = sum;
}
} while (std::next_permutation(digits, digits + 4));
return minSum;
}
int main() {
int num = 2932;
std::cout << minimumSum(num) << std::endl;
return 0;
}function* permute(permutation) {
let length = permutation.length, c = Array(length).fill(0), i = 1, k, p;
yield permutation.slice();
while (i < length) {
if (c[i] < i) {
k = i % 2 && c[i];
p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
yield permutation.slice();
} else {
c[i] = 0;
++i;
}
}
}
function minimumSum(num) {
const digits = num.toString().split('').map(Number);
let minSum = Infinity;
for (const perm of permute(digits)) {
let new1 = perm[0] * 10 + perm[1];
let new2 = perm[2] * 10 + perm[3];
minSum = Math.min(minSum, new1 + new2);
}
return minSum;
}
const num = 2932;
console.log(minimumSum(num));#include <stdio.h>
int computeSum(int a, int b, int c, int d) {
int new1 = a * 10 + b;
int new2 = c * 10 + d;
return new1 + new2;
}
int minimumSum(int num) {
int digits[4] = {(num / 1000) % 10, (num / 100) % 10, (num / 10) % 10, num % 10};
int minSum = 10000; // Larger than any possible sum
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if (i == j) continue;
for (int k = 0; k < 4; ++k) {
if (k == i || k == j) continue;
for (int l = 0; l < 4; ++l) {
if (l == i || l == j || l == k) continue;
int sum = computeSum(digits[i], digits[j], digits[k], digits[l]);
if (sum < minSum) {
minSum = sum;
}
}
}
}
}
return minSum;
}
int main() {
int num = 2932;
printf("%d\n", minimumSum(num));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public static int MinimumSum(int num) {
List<int> digits = new List<int> {
(num / 1000) % 10, (num / 100) % 10, (num / 10) % 10, num % 10
};
int minSum = int.MaxValue;
digits.Sort();
do {
// There is no next permutation in C#, so consider using recursion or manual permutation logic
int sum = (digits[0] * 10 + digits[1]) + (digits[2] * 10 + digits[3]);
minSum = Math.Min(minSum, sum);
} while (NextPermutation(digits));
return minSum;
}
public static void Main() {
int num = 2932;
Console.WriteLine(MinimumSum(num));
}
private static bool NextPermutation(List<int> lst) {
int i = lst.Count - 1;
while (i > 0 && lst[i - 1] >= lst[i]) i--;
if (i <= 0)
return false;
int j = lst.Count - 1;
while (lst[j] <= lst[i - 1]) j--;
int temp = lst[i - 1];
lst[i - 1] = lst[j];
lst[j] = temp;
j = lst.Count - 1;
while (i < j) {
temp = lst[i];
lst[i] = lst[j];
lst[j] = temp;
i++;
j--;
}
return true;
}
}Python's itertools.permutations generates all permutations of the digit list. We evaluate each permutation to determine the smallest sum of any two possible new numbers formed this way.
Time Complexity: O(1), due to constant-size operations.
Space Complexity: O(1), utilizes a fixed number of variables.
Approach 3: Default Approach
function minimumSum(num: number): number {
const nums = new Array(4).fill(0);
for (let i = 0; i < 4; i++) {
nums[i] = num % 10;
num = Math.floor(num / 10);
}
nums.sort((a, b) => a - b);
return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];
}func minimumSum(num int) int {
var nums []int
for num > 0 {
nums = append(nums, num%10)
num /= 10
}
sort.Ints(nums)
return 10*(nums[0]+nums[1]) + nums[2] + nums[3]
}impl Solution {
pub fn minimum_sum(mut num: i32) -> i32 {
let mut nums = [0; 4];
for i in 0..4 {
nums[i] = num % 10;
num /= 10;
}
nums.sort();
10 * (nums[0] + nums[1]) + nums[2] + nums[3]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Minimal Pairing | Time Complexity: O(1), due to constant operations on four digits. |
| Brute Force Combination | Time Complexity: O(1), due to constant-size operations. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Combination | O(1) | O(1) | Good for understanding the search space or verifying correctness when digits are very small in count. |
| Sorting and Minimal Pairing (Greedy) | O(d log d) | O(1) | Preferred solution. Uses sorting to place the smallest digits in the highest positional weights to minimize total sum. |
Frequently asked questions
Is Minimum Sum of Four Digit Number After Splitting Digits easy or hard?
LeetCode classifies this problem as Easy. The challenge mainly tests basic digit manipulation, sorting, and recognizing a greedy placement strategy rather than complex data structures or algorithms.
Minimum Sum of Four Digit Number After Splitting Digits Python/Java solution
In Python or Java, extract digits using modulo and division, store them in a list or array, sort the digits, then compute (10*d0 + d2) + (10*d1 + d3). The implementation is only a few lines because the greedy arrangement directly gives the minimal sum.
How to solve Minimum Sum of Four Digit Number After Splitting Digits in O(n)?
Since there are only four digits, you can treat the problem as constant time. In a generalized version with more digits, you would extract digits in O(n) and sort them in O(n log n). After sorting, greedily distribute digits between the two numbers to balance place values and minimize the sum.
What is the best approach for Minimum Sum of Four Digit Number After Splitting Digits?
The optimal approach uses greedy sorting. Extract the four digits, sort them, and distribute the smallest digits into the tens place of two numbers. After sorting digits d0 ≤ d1 ≤ d2 ≤ d3, construct numbers (10*d0 + d2) and (10*d1 + d3). This ensures the smallest digits contribute to the highest positional value, minimizing the total sum.
Is Minimum Sum of Four Digit Number After Splitting Digits asked at Google/Amazon/Meta?
This problem represents a typical easy-level greedy and digit manipulation pattern. Variations of digit rearrangement and greedy placement frequently appear in interviews at companies like Amazon and Google, especially in early screening rounds or coding assessments.
What data structure is used in Minimum Sum of Four Digit Number After Splitting Digits?
The solution typically uses a small array or list to store the digits of the number. After extracting digits with modulo and division operations, the array is sorted and used to construct the two resulting numbers.
What is the time complexity of Minimum Sum of Four Digit Number After Splitting Digits?
The greedy solution runs in O(d log d) time due to sorting the digits, where d is the number of digits. Since the problem always has four digits, this effectively becomes constant time in practice. Space complexity is O(1) because only a small fixed array of digits is stored.