Minimum Sum of Two Numbers Formed from Digits of an Array in O(n)

Table of Contents#

Introduction
Problem Statement
Intuition and Insight
Algorithm Selection: Frequency Array and Moving Pointer
Why Avoid Explicit Sorting?
Detailed O(n) Algorithm
Handling Leading Zeros
Time Complexity Analysis
Space Complexity Analysis
Example Walkthrough
Common Practices and Best Practices
Edge Cases
Implementation in Python
References

Problem Statement#

Given an array arr of length n where each element is a digit (0–9), construct two numbers A and B by partitioning the digits arbitrarily such that:

Every digit in arr is used exactly once.
The sum A + B is minimized.

Constraints:

Must run in O(n) time.
Must use O(n) extra space (for storing digits in lists).

Intuition and Insight#

The minimal sum is achieved by:

Minimizing Most Significant Digits (MSD): Assign the smallest available digits to the MSD positions of the two numbers to reduce their overall magnitude.
Balanced Digit Distribution: Alternate digit assignment between the two numbers to balance their lengths. This prevents one number from becoming disproportionately large.
Greedy Assignment: Process digits in sorted order (0–9) to ensure the smallest digits are used first, optimizing the sum.

Key observation: Any explicit sorting would be O(n log n), which is inefficient for constraints. Instead, we use a frequency array to simulate sorted order in O(n).

Algorithm Selection: Frequency Array and Moving Pointer#

Frequency Array: Count occurrences of each digit (0–9) in O(n) time.
Moving Pointer (min_avail): Track the smallest digit available at any point, initialized to 0. This avoids rebuilding a sorted array.
Alternate Assignment: Assign each digit from min_avail to either A or B in alternating turns. After assigning, decrement its frequency and advance min_avail if exhausted.
Digit to Number Conversion: Use strings to avoid expensive arithmetic during digit assembly, ensuring O(n) conversion to integers.

Why Avoid Explicit Sorting?#

Explicit sorting (e.g., comparison-based sort) is O(n log n) for an array of n digits.
Counting sort could work for digits (fixed range 0–9), but requires O(n) space for the output array and adds memory allocation overhead for large n.
Solution: Simulate sorted traversal using a frequency array and moving min_avail pointer:
- Total steps for pointer advancement: At most 10 (digits 0–9) over the entire loop (amortized O(1)).

Detailed O(n) Algorithm#

Frequency Counting:
- Initialize an array freq of size 10 (for digits 0–9).
- For each digit in arr, increment freq[d].
Digit Assignment:
- Initialize empty lists listA and listB for digits of the two numbers.
- min_avail = 0: Tracks the smallest available digit.
- turn = 0: Alternates assignment (0 for A, 1 for B).
- For each of the n digits:
  - Advance min_avail until a digit with freq[min_avail] > 0 is found.
  - Assign digit d = min_avail to listA (if turn==0) or listB (if turn==1).
  - Decrement freq[d] and toggle turn.
Number Conversion:
- Convert listA and listB to integers via string conversion to avoid expensive arithmetic.

Handling Leading Zeros#

Issue: Digits assigned to MSD positions could be zero, but integers ignore leading zeros.
Solution: Assign 0 to A or B even if it’s the first digit. During conversion, int('0...0') evaluates to 0. Example:
- listA = [0,0,2] → int("002") → 2.
This is valid since 002 simplifies to 2.

Time Complexity Analysis#

Frequency Counting: O(n).
Digit Assignment:
- min_avail moves forward (0→9) at most 10 times (amortized O(1) per digit).
- Total: O(n).
String Conversion:
- join and int conversion for lists of size k and m is O(k) + O(m) = O(n).
Total: O(n).

Space Complexity Analysis#

Frequency Array: O(1) (fixed-size 10).
Digit Lists: O(n) (storage for listA and listB).
Strings: O(n) for strings, freed after conversion.
Total Auxiliary Space: O(n).

Example Walkthrough#

Example 1: `[1, 2, 3, 4]`#

Frequency Array: [0,1,1,1,1,0,0,0,0,0]
Assign Turns:
- Turn 0: d=1 → A=[1]
- Turn 1: d=2 → B=[2]
- Turn 0: d=3 → A=[1,3]
- Turn 1: d=4 → B=[2,4]
Numbers: A=13, B=24 → Sum = 37.

Example 2: `[0, 0, 0, 1, 2]`#

Frequency Array: [3,1,1,0,0,0,0,0,0,0]
Assign Turns:
- Turn 0: d=0 → A=[0]
- Turn 1: d=0 → B=[0]
- Turn 0: d=0 → A=[0,0]
- Turn 1: d=1 → B=[0,1]
- Turn 0: d=2 → A=[0,0,2]
Numbers: A = int("002") = 2, B = int("01") = 1 → Sum = 3.

Common Practices and Best Practices#

Frequency Array Initialization: Use fixed-size arrays (size=10) for digit counting.
Pointer Optimization: Use min_avail to skip empty digits efficiently.
Avoid Big Integers: Use string conversion to prevent O(n²) arithmetic overhead.
Handling Invalid Digits: Skip or validate inputs to avoid undefined behavior.
Edge Cases:
- All Zeros: Result is 0 (e.g., A=0, B=0).
- Single Number: One number will be all digits, the other 0.

Edge Cases#

Empty Array: Return 0.
Single Digit: Assign to A, B=0.
All Zeros: A=0, B=0 → Sum=0.
Invalid Digits: Skip non-0–9 inputs.

Implementation in Python#

def min_sum(arr):
    n = len(arr)
    if n == 0:
        return 0
        
    freq = [0] * 10
    for d in arr:
        if 0 <= d <= 9:
            freq[d] += 1
    
    listA = []
    listB = []
    turn = 0
    min_avail = 0
    for _ in range(n):
        # Advance min_avail to next available digit
        while min_avail < 10 and freq[min_avail] == 0:
            min_avail += 1
        if min_avail == 10:
            break  # Safety break
            
        d = min_avail
        if turn == 0:
            listA.append(d)
        else:
            listB.append(d)
            
        freq[d] -= 1
        turn ^= 1  # Toggle between 0 and 1
        
    # Convert lists to integers via strings
    a_val = 0
    if listA:
        a_str = ''.join(str(d) for d in listA)
        a_val = int(a_str)
    b_val = 0
    if listB:
        b_str = ''.join(str(d) for d in listB)
        b_val = int(b_str)
    
    return a_val + b_val
 
# Example usage:
print(min_sum([1, 2, 3, 4]))  # Output: 37
print(min_sum([0, 0, 0, 1, 2]))  # Output: 3
print(min_sum([]))  # Output: 0

References#

GeeksforGeeks: Minimum Sum of Two Numbers Formed from Digits of an Array
Counting Sort: Wikipedia
Amortized Complexity: Amortized Analysis