2578

2578. Split With Minimum Sum (Easy)

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.

  <ul>
  	<li>In other words, the sum of the number of occurrences of each digit in <code>num1</code> and <code>num2</code> is equal to the number of occurrences of that digit in <code>num</code>.</li>
  </ul>
  </li>
  <li><code>num1</code> and <code>num2</code> can contain leading zeros.</li>
  

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.

 

Example 1:

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:

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 <= 109

Companies: Amazon

Related Topics:
Math, Greedy, Sorting

Similar Questions:

• Partition Equal Subset Sum (Medium)
• Minimum Cost to Move Chips to The Same Position (Easy)
• Partition Array Into Two Arrays to Minimize Sum Difference (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/split-with-minimum-sum
// Author: github.com/lzl124631x
// Time: O(KlogK) where K is the number of digits in num
// Space: O(K)
class Solution {
public:
    int splitNum(int num) {
        string s = to_string(num), a, b;
        sort(begin(s), end(s));
        for (int i = 0; i < s.size(); i += 2) {
            a += s[i];
            if (i + 1 < s.size()) b += s[i + 1];
        }
        return stoi(a) + stoi(b);
    }
};