Problem Description

You are given a positive integer num. Your task is to split this number into two non-negative integers num1 and num2 such that:

1. When you concatenate all the digits from num1 and num2 together, they form a permutation of the original number num. This means that the combined digits of num1 and num2 must use exactly the same digits as num, with the same frequency. For example, if num has three 2's and one 5, then num1 and num2 together must also have exactly three 2's and one 5.

2. Both num1 and num2 can have leading zeros. For instance, if you split 102 into 01 and 2, that's allowed.

3. The original number num is guaranteed not to have leading zeros.

4. The digits in num1 and num2 don't need to appear in the same order as they appear in num.

Your goal is to find the split that minimizes the sum num1 + num2 and return this minimum sum.

For example, if num = 4325, you could split it into 24 and 35 (using digits 4,2,3,5), giving a sum of 24 + 35 = 59. This happens to be the minimum possible sum for this number.

The key insight is that to minimize the sum, you should distribute the digits as evenly as possible between the two numbers, and arrange them from smallest to largest to minimize the value of each number.

Intuition

To minimize the sum of two numbers, we need to think about what makes a number small. A number is smaller when:

1. It has fewer digits
2. Its most significant (leftmost) digits are as small as possible

Since we must use all digits from the original number, we can't reduce the total number of digits. However, we can control how we distribute them. If we have n digits total, the best distribution is to split them as evenly as possible - giving each number approximately n/2 digits. This ensures neither number becomes unnecessarily large.

Next, within each number, we want the smallest available digits to occupy the most significant positions. For example, if we have digits [1, 2, 3, 4], we'd rather form 12 and 34 than 13 and 24, because 12 + 34 = 46 while 13 + 24 = 37.

This leads us to a greedy strategy:

1. Sort all available digits in ascending order
2. Alternately distribute these sorted digits between num1 and num2
3. Each number gets built by appending digits from smallest to largest

The alternating distribution ensures balanced lengths, while processing digits in sorted order ensures each number is built with its smallest possible value. For instance, with digits [1, 2, 3, 4, 5], we'd give 1 to num1, 2 to num2, 3 to num1, 4 to num2, and 5 to num1, resulting in num1 = 135 and num2 = 24.

The solution uses i & 1 to alternate between the two numbers (when i is even, i & 1 = 0; when odd, i & 1 = 1), and builds each number by multiplying the current value by 10 and adding the new digit.

Learn more about Greedy, Math and Sorting patterns.

Solution Approach

The implementation follows a counting and greedy approach:

Step 1: Count the digits We first extract and count all digits from num using a Counter (hash table). We process the number digit by digit using modulo and integer division:

• num % 10 gives us the last digit
• num //= 10 removes the last digit
• We also track n, the total number of digits

Step 2: Initialize the result array We create an array ans = [0, 0] to store our two numbers num1 and num2.

Step 3: Distribute digits greedily We iterate n times (once for each digit we need to place):

• We use a pointer j starting from 0 (smallest possible digit)
• For each iteration i:
  • We find the next available digit by checking while cnt[j] == 0: j += 1
  • Once we find an available digit j, we decrement its count: cnt[j] -= 1
  • We add this digit to one of our numbers using alternation: ans[i & 1]
  • The expression i & 1 alternates between 0 and 1 as i increases
  • We build the number by: ans[i & 1] = ans[i & 1] * 10 + j

Step 4: Return the sum Finally, we return sum(ans), which gives us num1 + num2.

Example walkthrough with num = 4325:

1. Count digits: {2:1, 3:1, 4:1, 5:1}, n = 4
2. Initialize: ans = [0, 0]
3. Distribute:
   • i=0: Find digit 2, add to ans[0] → ans = [2, 0]
   • i=1: Find digit 3, add to ans[1] → ans = [2, 3]
   • i=2: Find digit 4, add to ans[0] → ans = [24, 3]
   • i=3: Find digit 5, add to ans[1] → ans = [24, 35]
4. Return: 24 + 35 = 59

The time complexity is O(d log d) where d is the number of digits (due to the implicit sorting through ordered traversal), and space complexity is O(1) since we only use a fixed-size counter for digits 0-9.

Example Walkthrough

Let's walk through the solution with num = 532:

Step 1: Extract and count digits

• Start with num = 532
• Extract digits: 532 → 2 (532 % 10), then 53 → 3, then 5 → 5
• Counter: {2:1, 3:1, 5:1}, total digits n = 3

Step 2: Initialize result array

• ans = [0, 0] to store our two numbers

Step 3: Distribute digits alternately (smallest first)

• Iteration i=0:

  • Start searching from digit 0
  • Skip 0,1 (count=0), find digit 2 (count=1)
  • Add to ans[0 & 1] = ans[0]: ans[0] = 0 * 10 + 2 = 2
  • Decrement count of 2: {2:0, 3:1, 5:1}
  • Result: ans = [2, 0]

• Iteration i=1:

  • Continue from digit 2, skip it (count=0)
  • Find digit 3 (count=1)
  • Add to ans[1 & 1] = ans[1]: ans[1] = 0 * 10 + 3 = 3
  • Decrement count of 3: {2:0, 3:0, 5:1}
  • Result: ans = [2, 3]

• Iteration i=2:

  • Continue from digit 3, skip it (count=0)
  • Skip digit 4 (count=0), find digit 5 (count=1)
  • Add to ans[2 & 1] = ans[0]: ans[0] = 2 * 10 + 5 = 25
  • Decrement count of 5: {2:0, 3:0, 5:0}
  • Result: ans = [25, 3]

Step 4: Calculate minimum sum

• Return 25 + 3 = 28

This gives us the split num1 = 25 and num2 = 3, which uses all digits from 532 and achieves the minimum possible sum.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of digits in num. The algorithm performs two main operations:

• First loop: Extracts each digit from num and counts them, which takes O(n) time since we process each digit once.
• Second loop: Iterates exactly n times to distribute digits between two numbers. Although there's a nested while loop to find non-zero counts, each digit in the counter is decremented at most once across all iterations, making the total work still O(n).

The space complexity is O(C), where C is the number of distinct digits in num. Since we're dealing with decimal digits, C ≤ 10. The space is used for:

• The Counter object cnt which stores at most 10 different digit counts (0-9)
• The ans array of fixed size 2, which is O(1)
• A few integer variables (n, j, i), which are also O(1)

Therefore, the overall space complexity is O(C) where C ≤ 10, which can also be considered O(1) since it's bounded by a constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Inefficient Digit Counting with String Conversion

The Problem: Many developers instinctively convert the number to a string to count digits:

digit_count = Counter(str(num))  # Creates string keys '0'-'9', not integers

This creates several issues:

• String keys require conversion back to integers for arithmetic operations
• Additional memory overhead from string creation
• Slower performance due to string operations

The Solution: Use mathematical operations to extract digits directly:

digit_count = Counter()
while num > 0:
    digit_count[num % 10] += 1
    num //= 10

Pitfall 2: Not Resetting the Digit Pointer

The Problem: A common mistake is resetting current_digit = 0 inside the distribution loop:

for i in range(total_digits):
    current_digit = 0  # Wrong! This causes unnecessary iterations
    while digit_count[current_digit] == 0:
        current_digit += 1

This forces the algorithm to repeatedly scan through already-exhausted smaller digits, degrading performance from O(n) to O(n²) in worst cases.

The Solution: Keep current_digit outside the loop and never reset it:

current_digit = 0  # Initialize once
for i in range(total_digits):
    # current_digit maintains its position from previous iteration
    while digit_count[current_digit] == 0:
        current_digit += 1

Pitfall 3: Incorrect Alternation Pattern

The Problem: Using complex alternation logic or forgetting to alternate properly:

# Wrong approach 1: Always adding to the smaller number
if split_numbers[0] <= split_numbers[1]:
    split_numbers[0] = split_numbers[0] * 10 + current_digit
else:
    split_numbers[1] = split_numbers[1] * 10 + current_digit

# Wrong approach 2: Not alternating at all
split_numbers[0] = split_numbers[0] * 10 + current_digit

These approaches don't guarantee even distribution of digits or might not minimize the sum.

The Solution: Use simple index-based alternation with bitwise AND or modulo:

position = i & 1  # or i % 2
split_numbers[position] = split_numbers[position] * 10 + current_digit

Pitfall 4: Handling Edge Cases Incorrectly

The Problem: Not considering special cases like single-digit numbers or numbers with all identical digits:

# Might fail for num = 0 or num = 5
if num == 0:
    return 0  # Need to handle this explicitly

The Solution: The algorithm naturally handles these cases:

• Single digit (e.g., 5): Splits into 0 and 5, sum = 5
• All same digits (e.g., 222): Splits into 2 and 22, sum = 24
• The only special case needing attention is if the problem allows num = 0