Split With Minimum Sum

Easy
691.

Split With Minimum Sum

Split With Minimum Sum is an easy coding problem on math, sorting and greedy, asked in Amazon, TCS and Mindtree interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} num
 * @return {number}
 */
var splitNum = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Split With Minimum Sum — Solution in Python, Java & C++

Split With Minimum Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Split With Minimum Sum is an easy coding problem on math, sorting and greedy, asked in Amazon, TCS and Mindtree interviews.

  • Difficulty: Easy
  • Topics: Math, Sorting, Greedy
  • 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

Hints for Split With Minimum Sum

  1. Hint 1

    The smallest digits should carry the largest place values, so sort the digits ascending.

  2. Hint 2

    Split the sorted digits by alternating: one to the first number, one to the second.

  3. Hint 3

    That keeps both numbers as short as possible and puts the small digits in the high places.

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

  1. Extract the digits of num and sort them ascending.
  2. 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.
  3. 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

Java

public static int splitNum(int num) {
    char[] digits = String.valueOf(num).toCharArray();
    Arrays.sort(digits);
    int a = 0, b = 0;
    for (int i = 0; i < digits.length; i++) {
        int d = digits[i] - '0';
        if (i % 2 == 0) a = a * 10 + d;
        else b = b * 10 + d;
    }
    return a + b;
}

C++

int splitNum(int num) {
    string digits = to_string(num);
    sort(digits.begin(), digits.end());
    int a = 0, b = 0;
    for (size_t i = 0; i < digits.size(); i++) {
        int d = digits[i] - '0';
        if (i % 2 == 0) a = a * 10 + d;
        else b = b * 10 + 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Sorting Algorithms · Greedy Algorithms