Friday, November 7, 2014

Facebook: Multiply Strings

Given 2 very large numbers, each of which is so large that it can only be represented as an array of integers. Write a function to multiply them.

http://buttercola.blogspot.com/2014/09/leetcode-multiply-strings.html

Code (Java):
import java.util.*;
public class Solution {
    public int[] multiply(int[] a, int[] b) {
        if (a == null || a.length == 0) {
            int[] temp = new int[0];
            return temp;
        }
        
        if (b == null || b.length == 0) {
            int[] temp = new int[0];
            return temp;
        }
        
        List<Integer> result = new ArrayList<Integer>();
        int count = 0;
        for (int i = a.length - 1; i >= 0; i--) {
            List<Integer> buf = new ArrayList<Integer>();
            int carry = 0;
            for (int j = b.length - 1; j >= 0; j--) {
                carry += a[i] * b[j];
                
                buf.add(0, carry % 10);
                carry /= 10;
            }
            if (carry != 0) {
                buf.add(0, carry);
            }
            
            if (result.isEmpty()) {
                result.addAll(buf);
            } else {
                count++;
                result = addArray(buf, result, count);
            }
        }
        
        // convert the array list to array
        int[] ans = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            ans[i] = result.get(i);
        }
        
        return ans;
    }
    
    private List<Integer> addArray(List<Integer> buf, List&t;Integer> result, int count) {
        for (int i = 0; i < count; i++) {
            buf.add(0);
        }
        
        int p = buf.size() - 1;
        int q = result.size() - 1;
        List<Integer> temp = new ArrayList<Integer>();
        int carry = 0;
        
        while (p >= 0 || q >= 0) {
            if (p >= 0) {
                carry += buf.get(p);
                p--;
            }
            
            if (q >= 0) {
                carry += result.get(q);
                q--;
            }
            
            temp.add(0, carry % 10);
            carry /= 10;
        }
        
        if (carry == 1) {
            temp.add(0, 1);
        }
        
        return temp;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();
      
      int[] a = new int[]{9,9,9,9};
      int[] b = new int[]{9,9,9};

      int[] result = sol.multiply(a, b);
      
      for (Integer elem : result) {
        System.out.print(elem + " ");
      }

      System.out.println();
    }
}

No comments:

Post a Comment