Find factorial of a large number

The problem, simply

The factorial of n, written n!, is 1 * 2 * 3 * ... * n. Give back n! as a string of digits.

The catch: it grows very fast. 20! already has 19 digits, and 100! has 158. No built in number type can hold that, so you must do the multiplying yourself. Below, d stands for the number of digits in the answer.

A story to remember it

Picture it

Examples

Way 1: the simple way

The first thing anyone tries: keep a long and multiply.

class Solution {
    public String factorial(int n) {
        long result = 1;
        for (int x = 2; x <= n; x++) {
            result *= x;              // silently wraps around after 20!
        }
        return String.valueOf(result);
    }
}

How long it takes: n multiplications, O(n). Extra room: one number, O(1). But it is only correct up to n = 20. After that the number wraps around and the answer is garbage, with no error. That is why this problem exists: we need a number that can grow as long as it wants.

Way 2: the clever way

Keep the answer as a list of digits, ones digit first. Multiply the whole list by x = 2, 3, ..., n, the school way.

1. Start with the list [1].
2. For each x, walk the boxes from the ones digit up. For each box: product = box * x + carry. Put product % 10 back in the box and carry product / 10.
3. After the last box, while the carry is not 0, add carry % 10 as a new box and divide the carry by 10.
4. At the end, read the boxes from last to first.

Storing the ones digit first means a new digit goes at the end of the list, which is cheap.

class Solution {
    public String factorial(int n) {
        List<Integer> digits = new ArrayList<>();
        digits.add(1);                                   // start with 1
        for (int x = 2; x <= n; x++) {
            int carry = 0;
            for (int i = 0; i < digits.size(); i++) {
                int product = digits.get(i) * x + carry; // one box times x, plus carry
                digits.set(i, product % 10);             // keep the last digit
                carry = product / 10;                    // pass the rest on
            }
            while (carry > 0) {                          // leftover carry: new boxes
                digits.add(carry % 10);
                carry /= 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = digits.size() - 1; i >= 0; i--) sb.append(digits.get(i));
        return sb.toString();
    }
}

How long it takes: for each of the n multipliers we walk at most d boxes, so O(n * d). Since n! has about n * log10(n) digits, that is about O(n^2 log n). Extra room: the d boxes, O(d).

Another way: bigger boxes

Nothing says a box must hold one digit. Let each box hold 9 digits, a number from 0 to 999,999,999. Use long for the product so box * x + carry cannot overflow. There are 9 times fewer boxes, so it runs about 9 times faster, with the same O(n * d) shape. When printing, pad every box except the first with zeros to 9 digits.

class Solution {
    public String factorial(int n) {
        final int BASE = 1_000_000_000;               // 9 digits per box
        List<Integer> boxes = new ArrayList<>();
        boxes.add(1);
        for (int x = 2; x <= n; x++) {
            long carry = 0;
            for (int i = 0; i < boxes.size(); i++) {
                long product = (long) boxes.get(i) * x + carry;
                boxes.set(i, (int) (product % BASE));
                carry = product / BASE;
            }
            while (carry > 0) {
                boxes.add((int) (carry % BASE));
                carry /= BASE;
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(boxes.get(boxes.size() - 1));       // the top box has no padding
        for (int i = boxes.size() - 2; i >= 0; i--) {
            sb.append(String.format("%09d", boxes.get(i)));
        }
        return sb.toString();
    }
}

In real Java code you can also use BigInteger, but interviewers want to see that you can do the carrying yourself.

Watch out for

• The leftover carry can have more than one digit when x is large (times 100 can leave a carry of 90 or more). Use a while loop, not a single if.
• With one digit boxes, box * x + carry stays below 10 * x, so int is safe for x up to about 200 million. With 9 digit boxes you need long.
• n = 0 and n = 1 must give "1". Starting from [1] handles both.

What interviewers ask next

• How many trailing zeros does n! have? Count the factors of 5: n/5 + n/25 + n/125 + .... For 100 that is 20 + 4 = 24.
• How many digits does n! have, without computing it? Add up log10(x) for x = 1..n, take the floor, and add 1.
• Multiply two huge numbers given as strings? Same carrying idea with two nested loops: digit i times digit j lands in box i + j.
• Can factorials be computed faster? Multiply in a balanced tree (pairs, then pairs of pairs) so the big multiplications are between numbers of similar size, and use fast multiplication. That is how BigInteger libraries do it.
• What is n! mod (10^9 + 7)? Then no big numbers are needed: take the remainder after every multiplication.

Remember this

Grown-up words: the boxes are an arbitrary precision (big integer) number in base 10, carrying is schoolbook multiplication, the 9 digit boxes are base 10^9 limbs, and the wrap around in Way 1 is integer overflow.