ARRANGE - Arranging Amplifiers

The problem, simply

You have n amplifiers with whole number factors a[i]. A signal of strength 1 goes through all of them, one after another, in an order you choose. An amplifier with factor A turns a signal of strength X into A^X.

Give back the order that makes the final signal as strong as possible. (This is SPOJ ARRANGE.) If several orders tie, any of them is fine.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order and keep the strongest final signal. The numbers get far too big to store, so store each one as "e to the e to the ... to the x": a count of how many e^ there are, and a small x. Comparing two giants is then easy: more layers wins, and on equal layers the bigger x wins.

class Solution {
    // value = e^(e^(...e^(x))) with lvl layers
    static final class Big {
        final int lvl; final double x;
        Big(int lvl, double x) {
            double l50 = Math.log(50);
            while (x > 50) { x = Math.log(x); lvl++; }          // push big x up a layer
            while (lvl > 0 && x < l50) { x = Math.exp(x); lvl--; } // pull small x down
            this.lvl = lvl; this.x = x;
        }
        int compareTo(Big o) {
            if (lvl != o.lvl) return Integer.compare(lvl, o.lvl);
            if (Math.abs(x - o.x) < 1e-9 * Math.max(1, Math.abs(x))) return 0;
            return Double.compare(x, o.x);
        }
    }

    // p raised to the power v
    static Big pow(int p, Big v) {
        if (p == 1) return new Big(0, 1);
        double lp = Math.log(p), c = Math.log(lp);
        if (v.lvl == 0) return new Big(1, v.x * lp);
        if (v.lvl == 1) return new Big(2, v.x + c);
        if (v.lvl == 2) return new Big(3, Math.log(Math.exp(v.x) + c));
        return new Big(v.lvl + 1, v.x);                         // c is too tiny to matter
    }

    private int[] best;
    private Big bestVal;

    public int[] arrange(int[] a) {
        best = a.clone();
        bestVal = null;
        permute(a.clone(), 0);
        return best;
    }

    private void permute(int[] a, int k) {
        if (k == a.length) {
            Big v = new Big(0, 1);
            for (int f : a) v = pow(f, v);                      // the signal goes through
            if (bestVal == null || v.compareTo(bestVal) > 0) { bestVal = v; best = a.clone(); }
            return;
        }
        for (int i = k; i < a.length; i++) {
            int t = a[k]; a[k] = a[i]; a[i] = t;
            permute(a, k + 1);
            t = a[k]; a[k] = a[i]; a[i] = t;
        }
    }
}

How long it takes: n! orders, each pushed through n amplifiers, O(n! * n). Extra room: O(n). Good for checking the rule on small inputs, hopeless for real ones.

Way 2: the clever way

Three rules, found by thinking about the tower of powers and checked against Way 1 on every input of up to six amplifiers.

1. All the 1s go first. While the signal is 1, a 1 keeps it at 1 and loses nothing. Anywhere later, a 1 would crush the signal back to 1.
2. The rest go from biggest to smallest. The last amplifier is the base of the tower, and everything before it builds the exponent. A small base under a giant exponent beats a big base under a smaller one, for example 2^(3^4) = 2^81 against 4^(3^2) = 4^9.
3. If, after the 1s, the order starts with a 3 followed by a 2, swap those two. 3^2 = 9 beats 2^3 = 8, and every amplifier after them only makes a bigger start count more.

class Solution {
    public int[] arrange(int[] a) {
        int n = a.length, ones = 0;
        List<Integer> rest = new ArrayList<>();
        for (int x : a) {
            if (x == 1) ones++;
            else rest.add(x);
        }
        rest.sort(Collections.reverseOrder());               // biggest first
        if (rest.size() >= 2 && rest.get(0) == 3 && rest.get(1) == 2) {
            rest.set(0, 2);                                   // 2 then 3 beats 3 then 2
            rest.set(1, 3);
        }

        int[] out = new int[n];
        int k = 0;
        for (int i = 0; i < ones; i++) out[k++] = 1;         // the 1s go first
        for (int x : rest) out[k++] = x;
        return out;
    }
}

How long it takes: the sort, O(n log n). Extra room: the output, O(n).

Watch out for

• Sorting with a "compare a^b against b^a" rule mixes up which end is the base and gets cases like [2, 3, 4] wrong.
• Never compute the real values. They have more digits than there are atoms in the universe.
• 2 and 4 tie (2^4 = 4^2), so their order does not matter. Do not let a tie break your sort.
• The input can have 100,000 amplifiers. Sorting is fine; trying orders is not.

What interviewers ask next

• Why must the base be small? Compare x^(y^Z) with y^(x^Z) for a huge Z: the exponent dominates. The bigger number should sit higher in the tower, where it multiplies the exponent.
• How can you test such a rule without huge numbers? Store values as layers of logs, as in Way 1, and compare layers first. Or compare log(log(value)) when you know the numbers are big.
• What other problems sort by a custom rule? "Largest number" from a list of numbers sorts by comparing a + b against b + a as strings. The danger is the same: prove that your rule is a real ordering before you trust it.
• What changes if the signal started at 0? Then A^0 = 1 for every amplifier, so the first amplifier is wasted and the rule shifts by one place.

Remember this

Grown-up words: the stacked powers are a power tower (tetration style growth), the last amplifier is the base, the layers of e^ are iterated logarithms, and the three rules are a custom sort order.