Teaching Kids Programming – Split With Minimum Sum (Heap, Priority Queue)

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 (Heap, Priority Queue)

We can build a heap via heapify in Python. A Heap is a data structure like trees, where the root is the min or max. In Python, a heap is a min heap meaning the heappop pops the next smallest element from the heap in O(LogN) time.

We can heappush to push a new element to the heap. The heapify time complexity is O(N) if we are directly building a heap from a given list. However, if we push N elements by heappush, this will take O(NLogN) time as the heappush is O(LogN) time complexity.

So, we take the digits by turn using the heappop if there is more digits to take. The time complexity is O(NLogN).

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

class Solution:
    def splitNum(self, num: int) -> int:
        digits = list(str(num))
        s1 = 0
        s2 = 0
        heapify(digits)
        while digits:
            a = heappop(digits)
            s1 = s1 * 10 + int(a)
            if digits:
                b = heappop(digits)
                s2 = s2 * 10 + int(b)
        return s1 + s2

class Solution:
    def splitNum(self, num: int) -> int:
        digits = list(str(num))
        s1 = 0
        s2 = 0
        heapify(digits)
        while digits:
            a = heappop(digits)
            s1 = s1 * 10 + int(a)
            if digits:
                b = heappop(digits)
                s2 = s2 * 10 + int(b)
        return s1 + s2

The heappushpop is same as heappush and heappop while the heapreplace is equivalent as heappop and heappush. However, both heappushpop and heapreplace are more performant than the two operations combined.

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) —