Math Problems with Big Numbers

Given two positive numbers which are represented in strings, return the sum, difference, product, quotient and remainder of the two numbers.

A solution is to have the string converted to an array where digits are store in a reversed order and then do the calculation on each digit.

I. a + b

The implementation is quite straight-forward. Just be care of the carry.

public List<Integer> add(List<Integer> num1, List<Integer> num2) {
    List<Integer> sum = new ArrayList<>();
    int i = 0;
    int carry = 0;
    while (i < num1.size() || i < num2.size()) {
        int n = carry;
        if (i < num1.size()) {
            n += num1.get(i);
        }
        if (i < num2.size()) {
            n += num2.get(i);
        }
        i++;
        sum.add(n % 10);
        carry = n / 10;
    }
    if (carry > 0) {
        sum.add(carry);
    }
    return sum;
}

Leetcode: 2. Add Two Numbers.

II. a - b

Simplar to a + b, but be aware of the case when a is smaller than b. And don’t forget to remove the leading 0 in the difference.

// num1 must be larger than num2
private List<Integer> minus(List<Integer> num1, List<Integer> num2) {
    List<Integer> diff = new ArrayList<>();
    int carry = 0;
    for (int i = 0; i < num1.size(); i++) {
        int n = 10 + num1.get(i) - carry;
        if (i < num2.size()) {
            n = n - num2.get(i);
        }
        if (n < 10) {
            carry = 1;
        } else {
            n = n % 10;
            carry = 0;  // carry should be set to 0 here
        }
        diff.add(n);
    }
    // remove leading 0
    int i = diff.size() - 1;
    while (i > 0) {
        if (diff.get(i) == 0) {
            diff.remove(i);
        } else {
            break;
        }
        i--;
    }
    return diff;
}

III. a * b

The solution is to mimic the process of doing multiplication, but be aware of the the index.

private List<Integer> multiple(List<Integer> num1, List<Integer> num2) {
    List<Integer> product = new ArrayList<>(num1.size() + num2.size());
    // go through each digit in num1
    for (int i = 0; i < num1.size(); i++) {
        int carry = 0;
        for (int j = 0; j < num2.size(); j++) {
            // the currect index for the product is i + j
            int n = num1.get(i) * num2.get(j) + carry;
            if (i + j < product.size()) {
                n += product.get(i + j);
            }
            carry = n / 10;
            n = n % 10;
            // note: set(index, number) is used for replacement only
            if (i + j < product.size()) {
                product.set(i + j, n);
            } else {
                product.add(n);
            }
        }
        if (carry > 0) {
            product.add(carry);
        }
    }
    // remove leading 0
    int i = product.size() - 1;
    while (i > 0) {
        if (product.get(i) > 0) {
            break;
        }
        product.remove(i);
        i--;
    }
    return product;
}

LeetCode: 43. Multiply Strings

IV. a / b and a % b

The idea is to use subtraction - repeat the process of a minus b until a < b. But this whole process is time consuming. To improve performance, we don’t have to do a - b each time, but we can try something like a - b*10. For example, a = 2981, b = 13, because the difference between the length of a and b is 2, so the dividend can be initailized to be 1300, and when the divisor become less than dividend, a 0 can be removed from the dividend, as shown in the table below. This is actually how we do subtraction.

divisor	dividend	quotient	remainder
2981	1300	100	1681
1681	1300	200	381
381	130	210	251
251	130	220	121
121	13	…	…

// num2 cannot be a zero
private List<Integer> divide(List<Integer> num1, List<Integer> num2) {
    List<Integer> quotient = new ArrayList<>();
    quotient.add(0);

    int k = num1.size() - num2.size();
    List<Integer> dividend = buildDividend(num2, k);
    List<Integer> counter = buildCounter(k);
    while (compare(num1, num2) > 0) {
        while (compare(num1, dividend) >= 0) {
            num1 = minus(num1, dividend);
            quotient = add(quotient, counter);
        }
        dividend.remove(0);
        counter.remove(0);
    }
    // num1 is now the remainder
    return quotient;
}

private List<Integer> buildCounter(int zeroCount) {
    List<Integer> counter = new ArrayList<>();
    while (zeroCount > 0) {
        counter.add(0);
        zeroCount--;
    }
    counter.add(1);
    return counter;
}

private List<Integer> buildDividend(List<Integer> num, int zeroCount) {
    List<Integer> dividend = new ArrayList<>();
    while (zeroCount > 0) {
        dividend.add(0);
        zeroCount--;
    }
    for (int i = 0; i < num.size(); i++) {
        dividend.add(num.get(i));
    }
    return dividend;
}