Split With Minimum Sum

Difficulty: Easy | Acceptance: 73.50% | Paid: No Topics: Math, Greedy, Sorting

Given a positive integer num, split it into two non-negative integers new1 and new2 by using the digits of num.

Leading zeros are allowed, and all digits must be used.

Return the minimum possible sum of new1 and new2.

• Examples
• Constraints
• Sorting & Greedy
• Counting Sort
• Min-Heap

Examples

Input: num = 4325
Output: 59
Explanation: We can split 4325 into 24 and 35, and the sum is 59. 
24 + 35 = 59 is the minimum possible sum.

Input: num = 687
Output: 75
Explanation: We can split 687 into 68 and 07, and the sum is 75. 
68 + 07 = 75 is the minimum possible sum.

Constraints

10 <= num <= 10^9

Sorting & Greedy

Intuition To minimize the sum of two numbers formed by a fixed set of digits, we should distribute the digits as evenly as possible. The most significant digits of both numbers should be the smallest available digits to keep the overall magnitude low.

Steps

• Convert the number to a string and sort the digits in ascending order.
• Iterate through the sorted digits.
• Alternately append digits to new1 and new2. This ensures that the smallest digits occupy the highest place values in both numbers.
• Return the sum of new1 and new2.

class Solution:
    def splitNum(self, num: int) -> int:
        s = sorted(str(num))
        n1, n2 = 0, 0
        for i, c in enumerate(s):
            if i % 2 == 0:
                n1 = n1 * 10 + int(c)
            else:
                n2 = n2 * 10 + int(c)
        return n1 + n2

Complexity

• Time: O(N log N), where N is the number of digits in num. This is due to the sorting step.
• Space: O(N) to store the array/string of digits.
• Notes: Sorting is the most straightforward approach and is very fast given the constraint num <= 10^9 (max 10 digits).

Counting Sort

Intuition Since the digits are limited to 0-9, we can count the frequency of each digit instead of using a general-purpose sorting algorithm. This allows us to construct the numbers in linear time relative to the number of digits.

Steps

• Initialize an array count of size 10 with zeros.
• Iterate through the digits of num and increment the corresponding index in count.
• Iterate through the count array from 0 to 9.
• For each digit with a non-zero count, alternately add it to new1 and new2 until the count is exhausted.
• Return the sum.

class Solution:
    def splitNum(self, num: int) -> int:
        cnt = [0] * 10
        for d in str(num):
            cnt[int(d)] += 1
        
        n1, n2 = 0, 0
        turn = 0
        for d in range(10):
            while cnt[d] > 0:
                if turn == 0:
                    n1 = n1 * 10 + d
                    turn = 1
                else:
                    n2 = n2 * 10 + d
                    turn = 0
                cnt[d] -= 1
        return n1 + n2

Complexity

• Time: O(N), where N is the number of digits. We iterate through the digits once to count, and once through the fixed-size array (10) to build the numbers.
• Space: O(1), as the count array size is fixed at 10 regardless of input size.
• Notes: This is the most optimal approach theoretically, though for N=10, the difference from O(N log N) is negligible.

Min-Heap

Intuition A Min-Heap (Priority Queue) naturally provides the smallest available digit at any given time. We can repeatedly extract the two smallest digits and assign them to new1 and new2 respectively.

Steps

• Convert the number to a string and push all digits into a Min-Heap.
• Initialize new1 and new2 to 0.
• While the heap is not empty:
  • Pop the smallest digit and append it to new1.
  • If the heap is not empty, pop the next smallest digit and append it to new2.
• Return the sum.

import heapq

class Solution:
    def splitNum(self, num: int) -> int:
        digits = [int(d) for d in str(num)]
        heapq.heapify(digits)
        
        n1, n2 = 0, 0
        turn = 0
        while digits:
            d = heapq.heappop(digits)
            if turn == 0:
                n1 = n1 * 10 + d
                turn = 1
            else:
                n2 = n2 * 10 + d
                turn = 0
        return n1 + n2

Complexity

• Time: O(N log N), where N is the number of digits. Each insertion and extraction from the heap takes O(log N).
• Space: O(N) to store the heap.
• Notes: This approach is conceptually clean but has higher constant factors than simple sorting or counting sort for this specific problem size.