Problem

Given a positive integer num, split it into two non-negative integers num1 and num2 such that:

  • The concatenation of num1 and num2 is a permutation of num.
    • In other words, the sum of the number of occurrences of each digit in num1 and num2 is equal to the number of occurrences of that digit in num.
  • num1 and num2 can contain leading zeros.

Return the minimum possible sum of num1 and num2.

Notes:

  • It is guaranteed that num does not contain any leading zeros.
  • The order of occurrence of the digits in num1 and num2 may differ from the order of occurrence of num.

Examples

Example 1

1
2
3

Input: num = 4325
Output: 59
Explanation: We can split 4325 so that num1 is 24 and num2 is 35, giving a sum of 59. We can prove that 59 is indeed the minimal possible sum.

Example 2

1
2
3

Input: num = 687
Output: 75
Explanation: We can split 687 so that num1 is 68 and num2 is 7, which would give an optimal sum of 75.

Constraints

  • 10 <= num <= 10^9

Solution

Method 1 – Greedy Digit Distribution

Intuition

To achieve the minimum sum, distribute the digits of the number as evenly as possible between the two numbers, always assigning the smallest available digit to the number with the smaller current value.

Approach

  1. Convert the number to a list of its digits and sort them in ascending order.
  2. Initialize two numbers, num1 and num2, as empty strings.
  3. Iterate through the sorted digits, alternately appending each digit to num1 and num2.
  4. Convert num1 and num2 to integers and return their sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int splitNum(int num) {
        string s = to_string(num);
        sort(s.begin(), s.end());
        string a, b;
        for (int i = 0; i < s.size(); ++i) {
            if (i % 2 == 0) a += s[i];
            else b += s[i];
        }
        return stoi(a) + stoi(b);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import "sort"
func splitNum(num int) int {
    s := []byte(fmt.Sprintf("%d", num))
    sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
    a, b := "", ""
    for i, c := range s {
        if i%2 == 0 {
            a += string(c)
        } else {
            b += string(c)
        }
    }
    ai, _ := strconv.Atoi(a)
    bi, _ := strconv.Atoi(b)
    return ai + bi
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int splitNum(int num) {
        char[] s = Integer.toString(num).toCharArray();
        Arrays.sort(s);
        StringBuilder a = new StringBuilder(), b = new StringBuilder();
        for (int i = 0; i < s.length; ++i) {
            if (i % 2 == 0) a.append(s[i]);
            else b.append(s[i]);
        }
        return Integer.parseInt(a.toString()) + Integer.parseInt(b.toString());
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun splitNum(num: Int): Int {
        val s = num.toString().toCharArray().sorted()
        var a = ""
        var b = ""
        for (i in s.indices) {
            if (i % 2 == 0) a += s[i]
            else b += s[i]
        }
        return a.toInt() + b.toInt()
    }
}
1
2
3
4
5
6
7
8
9

def splitNum(num: int) -> int:
    s = sorted(str(num))
    a, b = '', ''
    for i, d in enumerate(s):
        if i % 2 == 0:
            a += d
        else:
            b += d
    return int(a) + int(b)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn split_num(num: i32) -> i32 {
        let mut s: Vec<char> = num.to_string().chars().collect();
        s.sort();
        let (mut a, mut b) = (String::new(), String::new());
        for (i, c) in s.iter().enumerate() {
            if i % 2 == 0 {
                a.push(*c);
            } else {
                b.push(*c);
            }
        }
        a.parse::<i32>().unwrap() + b.parse::<i32>().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    splitNum(num: number): number {
        const s = String(num).split('').sort();
        let a = '', b = '';
        for (let i = 0; i < s.length; ++i) {
            if (i % 2 === 0) a += s[i];
            else b += s[i];
        }
        return parseInt(a) + parseInt(b);
    }
}

Complexity

  • ⏰ Time complexity: O(d log d) – Sorting the digits, where d is the number of digits in num.
  • 🧺 Space complexity: O(d) – Space for digit arrays and strings.