Teaching Kids Programming – Split With Minimum Sum (Bucket Sorting Algorithm)

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 (Bucket Sorting Algorithm)

Given that we only have 10 digits, we can sort all the digits using bucket sorting which takes O(NK) time complexity where N is the number of digits and K is the number of buckets in this case 10 a constant and thus the overall time complexity is O(N).

We use 10 buckets aka Counters to count the number of each digit (from 0 to 9) appears, and then we construct two numbers by picking from the smallest digits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def splitNum(self, num: int) -> int:
        d = [0] * 10
        for i in str(num):
            d[int(i)] += 1
 
        s1 = 0
        s2 = 0
        i = 0
        while i < 10:
            if d[i] == 0:
                i += 1
                continue
            s1 = s1 * 10 + i
            d[i] -= 1
            while i < 10 and d[i] == 0:
                i += 1
            if i == 10:
                break
            s2 = s2 * 10 + i
            d[i] -= 1
 
        return s1 + s2

class Solution:
    def splitNum(self, num: int) -> int:
        d = [0] * 10
        for i in str(num):
            d[int(i)] += 1

        s1 = 0
        s2 = 0
        i = 0
        while i < 10:
            if d[i] == 0:
                i += 1
                continue
            s1 = s1 * 10 + i
            d[i] -= 1
            while i < 10 and d[i] == 0:
                i += 1
            if i == 10:
                break
            s2 = s2 * 10 + i
            d[i] -= 1

        return s1 + s2

When the counter (or bucket) is greater than 0, we can pick it, and decrement the counter, when the counter reaches zero, we move to the next larger digit until we use all the digits. The space complexity is O(1) as we are using constant 10 buckets. Bucket sorting algorithm is efficient and practical if we know the number of buckets is limited (small).

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