Friday, November 7, 2014

Facebook: Add up two big integers represented in arrays

Add up two big integers represented in arrays

Understand the problem:
1. Cannot transform the integers into int, then add. Might overflow.
2. So far let's consider the big integers are non-negative only.

Code (Java):


public class Solution {
    public int[] addTwoNum(int[] a, int[] b) {
        if (a == null || a.length == 0) {
            return b;
        }
        
        if (b == null || b.length == 0) {
            return a;
        }
        
        List<Integer> result = new ArrayList<Integer>();
        
        int carry = 0;
        int i = a.length - 1;
        int j = b.length - 1;
        while (i >=0 || j >= 0) {
            if (i >= 0) {
                carry += a[i];
                i--;
            }
            
            if (j >= 0) {
                carry += b[j];
                j--;
            }
            
            int digit = carry % 10;
            carry /= 10;
            result.add(0, digit);
        }
        
        if (carry == 1) {
            result.add(0, 1);
        }
        
        // arraylist to array
        int[] ans = new int[result.size()];
        for (int k = 0; k < result.size(); k++) {
            ans[k] = result.get(k);
        }
        
        return ans;
    }
}

No comments:

Post a Comment