Minimum sum of two numbers formed from digits of an array

The problem, simply

You get an array of digits, each from 0 to 9. Use every digit exactly once to build two numbers. Make the sum of the two numbers as small as possible, and return that sum.

For [6, 8, 4, 5, 2, 3] the best numbers are 246 and 358, and the answer is 604.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order of the digits and every place to cut the order into two numbers. Keep the smallest sum.

1. Make every order (permutation) of the digits.
2. For each order, try every cut point. The left part is one number, the right part is the other.
3. Keep the smallest sum seen.

class Solution {
    private long best;

    public long minSum(int[] digits) {
        best = Long.MAX_VALUE;
        if (digits.length == 0) return 0;
        permute(digits, 0);
        return best;
    }

    private void permute(int[] d, int start) {
        if (start == d.length) {
            for (int cut = 0; cut <= d.length; cut++) {          // left part is d[0..cut-1]
                best = Math.min(best, number(d, 0, cut) + number(d, cut, d.length));
            }
            return;
        }
        for (int i = start; i < d.length; i++) {
            swap(d, start, i);
            permute(d, start + 1);
            swap(d, start, i);
        }
    }

    private long number(int[] d, int from, int to) {
        long x = 0;
        for (int i = from; i < to; i++) x = x * 10 + d[i];
        return x;
    }

    private void swap(int[] d, int i, int j) { int t = d[i]; d[i] = d[j]; d[j] = t; }
}

How long it takes: n! orders, each with n + 1 cuts that cost O(n) to read, so O(n! * n^2). Already at 12 digits that is billions of steps. Extra room: the recursion, O(n).

Way 2: the clever way

Deal the cards smallest first, taking turns.

1. Put all digits into a min heap.
2. Poll digits one at a time. Odd turns go to the first number, even turns to the second: num = num * 10 + digit.
3. Return the sum of the two numbers.

Why it works: a digit in the front spot of a 3 digit number is worth 100, the next spot 10, the last spot 1. Taking turns keeps the two numbers the same length, so both have a 100 spot, both have a 10 spot, and so on. The two smallest digits get the two 100 spots, the next two get the 10 spots, and the biggest get the 1 spots. Any swap that puts a bigger digit in a more valuable spot makes the sum bigger.

import java.util.PriorityQueue;

class Solution {
    public long minSum(int[] digits) {
        PriorityQueue<Integer> cards = new PriorityQueue<>();  // min heap
        for (int d : digits) cards.offer(d);
        long first = 0, second = 0;
        boolean toFirst = true;
        while (!cards.isEmpty()) {
            int d = cards.poll();                 // smallest card left
            if (toFirst) first = first * 10 + d;
            else second = second * 10 + d;
            toFirst = !toFirst;                   // take turns
        }
        return first + second;
    }
}

How long it takes: n offers and n polls, O(n log n). Extra room: the heap, O(n). Sorting the array and dealing from left to right is the same idea with the same time.

Another way: count the digits, add as strings

Digits only go from 0 to 9, so you can count them instead of sorting: walk the counts from 0 to 9 and deal. With many digits the numbers do not fit in a long (18 digits are always safe), so build them as strings and add them digit by digit from the right, like on paper.

class Solution {
    public String minSum(int[] digits) {
        int[] count = new int[10];
        for (int d : digits) count[d]++;
        StringBuilder a = new StringBuilder(), b = new StringBuilder();
        boolean toA = true;
        for (int d = 0; d <= 9; d++) {
            for (int c = 0; c < count[d]; c++) {
                (toA ? a : b).append(d);          // deal smallest first
                toA = !toA;
            }
        }
        StringBuilder sum = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {   // paper addition from the right
            int s = carry;
            if (i >= 0) s += a.charAt(i--) - '0';
            if (j >= 0) s += b.charAt(j--) - '0';
            sum.append(s % 10);
            carry = s / 10;
        }
        while (sum.length() > 1 && sum.charAt(sum.length() - 1) == '0') {
            sum.setLength(sum.length() - 1);      // drop leading zeros (they are at the end before reversing)
        }
        return sum.length() == 0 ? "0" : sum.reverse().toString();
    }
}

This is O(n) time, and it is the version to give when the input can have thousands of digits.

Watch out for

• Do not split the sorted digits into a left half and a right half. [2, 3, 4, 5] split that way gives 23 + 45 = 68, but taking turns gives 24 + 35 = 59.
• Zeros are fine at the front of a number in math, but if you must print the numbers themselves, strip the leading zeros.
• An empty input should give 0, not crash.

What interviewers ask next

• Why taking turns and not two halves? A digit's value depends on its spot. Taking turns gives both numbers the same spots, so the smallest digits fill the two most valuable spots first.
• Can you do it in O(n)? Yes, count the ten digits instead of sorting, as in the last code block.
• What if you must build three numbers? Deal to three players in turn. The same argument works for any number of players.
• Return the two numbers, not only the sum? Return the two strings you built, and strip leading zeros before printing them.

Remember this

Grown-up words: the card pile is a min heap (priority queue), dealing smallest first is a greedy choice, the value of a spot is its place value, counting the ten digits is counting sort, and adding from the right with a carry is big number addition.