Teaching Kids Programming – Split With Minimum Sum (Sort the Digits, Greedy)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

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

Split With Minimum Sum (Sort the Digits, Greedy)

We can solve this problem by Greedy Algorithm. First, we need to sort the digits, and then we pick by turn the smallest digit for each number. We want to leave the larger digits to pick last.

We convert the integer value to string, and then break into list of characters (array), sort it, and then use the list comprehension to pick alternative digit for two numbers. [::2] means start from the first digit pick every other digit (1, 3, 5, 7 …). And [1::2] means start from the second digit and pick every other digit (2, 4, 6, …)

1
2
3
4

class Solution:
    def splitNum(self, num: int) -> int:
        s = sorted(list(str(num)))
        return int("".join(s[::2])) + int("".join(s[1::2]))

class Solution:
    def splitNum(self, num: int) -> int:
        s = sorted(list(str(num)))
        return int("".join(s[::2])) + int("".join(s[1::2]))

Time complexity is O(NLogN) where N is the number of the digits.

This problem can also be solved by Bucket Sorting, or Heap (Priority Queue).

Split With Minimum Sum

• Teaching Kids Programming – Split With Minimum Sum (Heap, Priority Queue)
• Teaching Kids Programming – Split With Minimum Sum (Sort the Digits, Greedy)
• Teaching Kids Programming – Split With Minimum Sum (Bucket Sorting Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —