HeapProblem 18 of 18
Minimum sum of two numbers formed from digits of an array
Problem Statement
Given an array of digits (0-9), form two numbers using these digits such that the sum of the two numbers is minimum. All digits must be used.
Example:
-
Input:
digits = [6, 8, 4, 5, 2, 3] -
Output:
604 -
Explanation:
- Two numbers: 358 and 246
- Sum = 358 + 246 = 604
-
Input:
digits = [5, 3, 0, 7, 4] -
Output:
82 -
Explanation:
- Two numbers: 35 and 47 (or 30 and 57, etc.)
- Optimal: 35 + 47 = 82
Approach 1: Generate All Permutations (Brute Force)
Intuition
Generate all possible ways to split digits into two groups, form numbers, and find minimum sum.
Algorithm
- Generate all permutations of digits
- For each permutation, split into two groups
- Form numbers and calculate sum
- Track minimum sum
java
import java.util.*;
public class Solution {
private int minSum;
private void permute(int[] digits, int start) {
if (start == digits.length) {
// Try all split points
for (int i = 0; i < digits.length - 1; i++) {
int num1 = formNumber(digits, 0, i);
int num2 = formNumber(digits, i + 1, digits.length - 1);
minSum = Math.min(minSum, num1 + num2);
}
return;
}
for (int i = start; i < digits.length; i++) {
swap(digits, start, i);
permute(digits, start + 1);
swap(digits, start, i);
}
}
private int formNumber(int[] digits, int start, int end) {
int num = 0;
for (int i = start; i <= end; i++) {
num = num * 10 + digits[i];
}
return num;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public int minSumBruteForce(int[] digits) {
minSum = Integer.MAX_VALUE;
permute(digits, 0);
return minSum;
}
}Complexity Analysis
- Time Complexity: O(n! * n) - n! permutations, O(n) to evaluate each
- Space Complexity: O(n) - For recursion and temporary storage
Approach 2: Greedy with Sorting (Optimal)
Intuition
To minimize the sum, we should:
- Make both numbers have similar number of digits (differ by at most 1)
- Place smaller digits at more significant positions
- Distribute sorted digits alternately between two numbers
Algorithm
- Sort digits in ascending order
- Distribute digits alternately to form two numbers
- Smaller digits go to higher positions (placed first)
- Handle leading zeros carefully
java
import java.util.Arrays;
public class Solution {
public int minSum(int[] digits) {
// Sort digits
Arrays.sort(digits);
int num1 = 0, num2 = 0;
// Distribute alternately
for (int i = 0; i < digits.length; i++) {
if (i % 2 == 0) {
num1 = num1 * 10 + digits[i];
} else {
num2 = num2 * 10 + digits[i];
}
}
return num1 + num2;
}
// Return as array [num1, num2, sum]
public int[] minSumNumbers(int[] digits) {
Arrays.sort(digits);
int num1 = 0, num2 = 0;
for (int i = 0; i < digits.length; i++) {
if (i % 2 == 0) {
num1 = num1 * 10 + digits[i];
} else {
num2 = num2 * 10 + digits[i];
}
}
return new int[]{num1, num2, num1 + num2};
}
}Complexity Analysis
- Time Complexity: O(n log n) - Dominated by sorting
- Space Complexity: O(1) - Sorting can be in-place (O(log n) for stack)
Approach 3: Using Min-Heap
Intuition
Use a min-heap to get smallest digits first. Alternately add to two numbers.
Algorithm
- Build min-heap from digits
- Extract minimum, add to current number
- Alternate between two numbers
- Continue until heap is empty
java
import java.util.PriorityQueue;
public class Solution {
public int minSum(int[] digits) {
// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int digit : digits) {
minHeap.offer(digit);
}
int num1 = 0, num2 = 0;
boolean first = true;
while (!minHeap.isEmpty()) {
int digit = minHeap.poll();
if (first) {
num1 = num1 * 10 + digit;
} else {
num2 = num2 * 10 + digit;
}
first = !first;
}
return num1 + num2;
}
}Complexity Analysis
- Time Complexity: O(n log n) - Building heap O(n), n extractions O(n log n)
- Space Complexity: O(n) - For the heap
Approach 4: Counting Sort Optimization
Intuition
Since digits are 0-9, use counting sort for O(n) sorting, then distribute.
Algorithm
- Count frequency of each digit (0-9)
- Iterate from 0 to 9, distribute digits alternately
- This avoids comparison-based sorting overhead
java
public class Solution {
public int minSum(int[] digits) {
// Count frequency of each digit
int[] count = new int[10];
for (int d : digits) {
count[d]++;
}
int num1 = 0, num2 = 0;
boolean first = true;
// Process digits from 0 to 9
for (int d = 0; d <= 9; d++) {
while (count[d] > 0) {
if (first) {
num1 = num1 * 10 + d;
} else {
num2 = num2 * 10 + d;
}
first = !first;
count[d]--;
}
}
return num1 + num2;
}
}Complexity Analysis
- Time Complexity: O(n) - Counting and distributing are both linear
- Space Complexity: O(1) - Only 10 counters regardless of input size
Key Takeaways
- Greedy approach: Smallest digits at most significant positions minimizes sum
- Balanced distribution: Both numbers should have similar number of digits
- Alternate assignment: Ensures balanced distribution automatically
- Counting sort: O(n) for digit-only input (0-9)
- Leading zeros don't matter in arithmetic operations
- For very large numbers, use strings instead of integers to avoid overflow
- This problem demonstrates practical application of sorting and greedy algorithms
- The heap approach shows flexibility but sorting is simpler and equally efficient