Multiply 2 no. represented by LL

The problem, simply

You get two linked lists. Each is a number, one digit per box, biggest digit first. So 9 -> 4 -> 6 is 946 and 8 -> 4 is 84.

Return the product of the two numbers. The lists can be hundreds of digits long, so the product can be far too big for a long. That is why the GeeksforGeeks version asks for the product modulo 1000000007: the remainder after dividing by 1000000007 (a big prime, written 10^9 + 7).

A story to remember it

Picture it

Examples

Way 1: the simple way

The first idea, building each number in a long and multiplying, breaks fast: a long holds about 19 digits, and even the product of two 10 digit numbers overflows. So do it the school way, digit by digit, and only wrap at the end.

1. Copy each list's digits into an array, ones digit first.
2. For every digit i of a and every digit j of b, add a[i] * b[j] into slot i + j of a result array.
3. Sweep the slots from the ones place up and pass carries along, so every slot holds one digit.
4. Read the exact product from the biggest digit down, wrapping by 1000000007 as you go.

class Solution {
    static final long MOD = 1_000_000_007L;

    public long multiplyTwoLists(Node first, Node second) {
        List<Integer> a = digits(first), b = digits(second);   // ones digit first
        int[] slot = new int[a.size() + b.size()];
        for (int i = 0; i < a.size(); i++)
            for (int j = 0; j < b.size(); j++)
                slot[i + j] += a.get(i) * b.get(j);            // school multiplication
        int carry = 0;
        for (int k = 0; k < slot.length; k++) {
            int v = slot[k] + carry;
            slot[k] = v % 10;
            carry = v / 10;
        }
        long ans = 0;
        for (int k = slot.length - 1; k >= 0; k--) ans = (ans * 10 + slot[k]) % MOD;
        return ans;
    }

    private List<Integer> digits(Node head) {
        List<Integer> d = new ArrayList<>();
        for (Node p = head; p != null; p = p.next) d.add(p.data);
        Collections.reverse(d);
        return d;
    }
}

How long it takes: every digit of a meets every digit of b, O(n m). Extra room: the digit arrays and slots, O(n + m). This is the right tool if the interviewer wants the exact product as a list, but it does far too much work when only the remainder is asked.

Way 2: the clever way

Use the clock. Reading a number left to right is "times 10, plus the next digit". We may wrap after every step, so the running number always stays below 1000000007.

1. Walk list a: x = (x * 10 + digit) % MOD.
2. Walk list b the same way to get y.
3. Return (x * y) % MOD. Both are below about 10^9, so their product is below about 10^18, which fits in a long.

With twelve 9s, the wrapping finally matters. After nine digits x is 999999999. The tenth digit would make 9999999999, which wraps to 999999936, and it stays small from then on:

class Solution {
    static final long MOD = 1_000_000_007L;

    public long multiplyTwoLists(Node first, Node second) {
        long x = 0, y = 0;
        for (Node p = first; p != null; p = p.next) x = (x * 10 + p.data) % MOD;   // wrap every digit
        for (Node q = second; q != null; q = q.next) y = (y * 10 + q.data) % MOD;
        return (x * y) % MOD;                                                      // fits in a long
    }
}

How long it takes: one walk over each list, O(n + m). Extra room: two numbers, O(1).

Watch out for

• Using int for x and y. Two numbers near 10^9 multiply to about 10^18, which needs a long.
• Multiplying three wrapped numbers at once, like x * y * z. That can reach 10^27 and overflow. Wrap after each multiplication.
• Leading zeros in a list, like 0 -> 0 -> 7. They are harmless here: they just keep x at 0 until the 7.
• Reading the digits in the wrong order. The head is the biggest digit, so "times 10 plus digit" walking from the head is right.

What interviewers ask next

• Return the full product as a linked list, no modulo. Use the school way from Way 1 and build the answer list from the slots, skipping leading zeros. O(n m).
• Can you multiply huge numbers faster than O(n m)? Karatsuba splits each number in halves and needs only three half size products instead of four, about O(n^1.58). Fast Fourier transform methods go to about O(n log n).
• Why is wrapping allowed? Because (a times b) mod M equals ((a mod M) times (b mod M)) mod M, and the same for adding. Remainders only care about remainders.
• Why 10^9 + 7? It is prime, it fits in an int, and the product of two such remainders still fits in a long.
• Add the two numbers modulo M instead. Same reading, then (x + y) % MOD.

Remember this

Grown-up words: the giant clock is modular arithmetic, 1000000007 is the modulus, wrapping is taking the remainder with %, reading digit by digit is Horner's method, and the school way is grade school long multiplication.