Split With Minimum Sum — Easy Problem & Solution

Split the digits of num into two positive integers num1 and num2 such that together they use every digit of num exactly once.

Difficulty: Easy
Topics: Math, Greedy, Sorting
Asked at: Amazon, TCS, Mindtree
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Split the digits of num into two positive integers num1 and num2 such that together they use every digit of num exactly once. Neither part needs to keep the original digit order, and leading zeros are allowed.

Return the minimum possible value of num1 + num2.

Example 1

Input: num = 4325
Output: 59
Explanation: Splitting into 24 and 35 gives 59, the smallest possible.

Example 2

Input: num = 687
Output: 75
Explanation: 68 and 7 give 75.

Example 3

Input: num = 9
Output: 9

Constraints

1 <= num <= 1000000000

How to solve Split With Minimum Sum

Two forces decide the answer: the two numbers should be as close as possible in length, and the smallest digits should sit in the highest places. Sorting ascending and dealing alternately achieves both at once.

Approach

Extract the digits of num and sort them ascending.
Deal them alternately: index 0 to num1, index 1 to num2, index 2 to num1, and so on, each time appending as the new least significant digit.
Return num1 + num2.

Why it works

A digit placed at position p contributes digit × 10^p. Alternating the deal makes the two numbers differ in length by at most one, which minimises the largest place value used; and dealing in ascending order pairs the smallest digits with the largest remaining places. Any exchange of two digits between positions of different weight increases the sum.

Complexity

Time — O(d log d) for d digits
Space — O(d)

Pitfalls

Giving one number all the small digits and the other all the large ones is worse — the lengths become unbalanced.
Leading zeros are explicitly allowed, so "05" is a legal part worth 5.

Reference solution

Python

def splitNum(num: int) -> int:
    digits = sorted(str(num))
    a = b = 0
    for i, d in enumerate(digits):
        if i % 2 == 0:
            a = a * 10 + int(d)
        else:
            b = b * 10 + int(d)
    return a + b

JavaScript

var splitNum = function(num) {
    var digits = String(num).split("").sort();
    var a = 0, b = 0;
    for (var i = 0; i < digits.length; i++) {
        var d = Number(digits[i]);
        if (i % 2 === 0) a = a * 10 + d;
        else b = b * 10 + d;
    }
    return a + b;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue