How do I multiply 2 big integers?

How do I multiply 2 big integers?
In the previous post I talked about "How do I add 2 big integers?". In the same scenario, consider that now you want to multiply those 2 huge integer numbers... Is the logic the same?

Yes, but the solution is not as simple. Please read the previous post to understand the logic behind the solution, then jump to the code and see my comments bellow.

[Java code snippet] Big integer product

First, note that we are iterating over both big integer representations as arrays – array1 and array2. On line 22 you can see the product of 2 single-digits items that represent the i-est and j-est digits of both big integers, respectively. 

As commented on line 25, if the product has 2 digits, the 2nd one should be stored in the next index. Since the current index is given by i+j, the next one will be i+j+1. To implement this logic, we will iterate over the array representation of this product, called prodAsArray, where k could be 0 or 1 (line 26).

When we are storing each digit on its correct position i+j+k (line 27), we have to add the it to the previous digit that might have been stored in a previous iteration. That's why I used +=. Ops, a sum operation, so the result could also have 2 digits! If it is the case, we have lines 30 to 38 to handle this, following the same logic as described before.

How do I add 2 big integers?

How do I add 2 big integers?
Say you want to add 2 integer numbers that are so huge that you can't just add them directly and you can't use an API like BigInteger; you have to implement the sum operation. What would you do?

The solution here is simple. Each huge integer number will be represented using an  int array[ ]. Each digit will be stored in a different position in the array. E.g.: 2012 --> [2, 1, 0, 2]

Considering that 2012 = (2*10^0 + 1*10^1 + 0*10^2 + 2*10^3 ),  then 2012 + 35= ((2+5)*10^0 + (1+3)*10^1 + (0+0)*10^2 + (2+0)*10^3 )   = 2047

So, all you have to do is to sum items in the same index, right?Almost! Remember to consider the carry: store it if the sum  > 9 and then use it in the next index sum. Well, enough of talking, let's see the code! First let's see the main() method and the add logic:

[Java code snippet] Big integer sum

 If you're interested in the details, take a look at the Big integer auxiliary methods, that also can be used for Big integer product, in a later post...

[Java code snippet] Big integer auxiliary methods

And here, the code so you can copy and run using Eclipse, NetBeans, etc.

package ric.interviewqa4java;

/** © 2012 interviewqa4java.blogspot.com */
public class BigInteger {
    public static void main(String[] args) {
        int bigInt1 = Integer.MAX_VALUE;
        int bigInt2 = Integer.MAX_VALUE;
   
        System.out.println(bigInt1+" + "+bigInt2+" = "+add(bigInt1, bigInt2));
    }
   
    public static String add(int bigInt1, int bigInt2) {
        //Find array length
        int length1 = intLenght(bigInt1);
        int length2 = intLenght(bigInt2);
        int arrayLength = Math.max(length1, length2);
               
        //convert numbers into array; Ex: 157 -> [7, 5, 1, 0, 0]
        int array1[] = intToArray(bigInt1, length1, arrayLength);
        int array2[] = intToArray(bigInt2, length2, arrayLength);
       
        //sum arrays
        return sumArray(array1, array2);
    }
   
    /** Solution logic here*/
    private static String sumArray(int[] array1, int[] array2) {
        int carry=0;
        int sumArray[] = new int[array1.length + 1];
       
        //sum arrays
        for (int i = 0; i < array1.length; i++) {
            sumArray[i] = (array1[i] + array2[i] + carry) % 10 ; //sum digits + carry; then extract last digit
            carry = (array1[i] + array2[i] + carry) / 10; //Compute carry
        }
        sumArray[array1.length] = carry;
        return arrayToString(sumArray);
    }
   
    /** Auxiliary methods*/
    private static int intLenght(int bigInt) {
        return Integer.toString(bigInt).length();
    }
    private static int[] intToArray(int bigInt, int bigIntLength, int arrayLength) {
       
        int array[] = new int[arrayLength ];
        for (int i = 0; i < arrayLength ; i++) {
            array[i] = ( i<bigIntLength ?
                             getDigitAtIndex(bigInt, bigIntLength - i -1) :
                             0 ); //complete the rest of the array with 0
        }
        return array;
    }
    private static int getDigitAtIndex(int longint,int index){       
        return Integer.parseInt(Integer.toString(longint).substring(index, index+1));
    }
    private static String arrayToString(int[] sumArray) {
        String sum = "";
        boolean firstNonZero = false;
        for (int i = sumArray.length-1; i >= 0 ; i--) { //from array end to beginning
           
            if(!firstNonZero && (sumArray[i]==0)){ //ignore if 1st digits are 0
                continue;
            } else{
                firstNonZero=true;
            }
            sum += sumArray[i];
            if((i%3 ==0)&&i!=0){ sum +=",";}  //formatting
        }
        String sumStr = sum.length()==0?"0":sum; // handle the 0 value (haha, input was not big!)
        return sumStr;
    }
}

Which sorting algorithm would you choose for guaranteed optimal time performance?

Which sorting algorithm would you choose for guaranteed optimal time performance?
Consider you have a huge array of n elements and you want to sort it in considering time performance, not only in the average case, but also in the worst case. Which sorting algorithm would I choose?

R: I won't go through all sort algorithms, so here my "quick answer": merge sort. Why? Because merge sort is O(n . lg n) not only for the average case, but also in the worst case. In addiction to that, merge sort doesn't replace the same array elements: it is stable.

Here is my Java code snippet. I removed unnecessary code from the picture, but it is shown bellow. Of course I just used a small array, feel free to used with a huge array!

[Java code snippet] Merge sort

package ric.interviewqa4java;

/** © 2012 interviewqa4java.blogspot.com */
public class MyMergeSort {
    static int array[]= {10,6,2,3,11,8,7,10,4,1};
   
    public static void main(String[] args) {       
        printlnArray("Original array = ");
        mergeSort(0, array.length-1);
        printlnArray("Sorted array   = ");
    }
   
    private static void mergeSort(int low, int high) {
        if(low<high){
            int middle = (low+high)/2;
            mergeSort(low, middle);
            mergeSort(middle+1, high);
            merge(low, middle, high);
        }// if i==j, the sub-list has 1 element, then it's considered sorted
    }
   
    private static void merge(int low, int middle, int high) {
       
        int tempArray[] = new int[high-low+1];
       
        //Compare members in each sublists in the the extreme left;
            //the smaller element is "removed" and
            //stored in a temporary list that will be an ordered list after the loop
        for(int i=low, j=middle+1, k=0; (i <= middle) || (j <= high); k++){
            if(i > middle){//all members in the left list were used
                tempArray[k] = array[j++];
            }
            else if (j > high){ //all member in the right list were used
                tempArray[k] = array[i++];
            }
            else if(array[i] <= array[j]){
                tempArray[k] = array[i++];
            }else{
                tempArray[k] = array[j++];
            }
        }
        //apply changes
        int index=low;
        for (Integer value : tempArray) {
            array[index++] = value;
        }
    }
   
    //Auxiliary method to print the array
    private static void printlnArray(String message) {
        StringBuffer arrayStr =  new StringBuffer(message+"[");
        for (int i = 0; i < array.length; i++) {
            arrayStr.append(array[i]);
            if(i < array.length-1){ arrayStr.append(", "); }
        }
        arrayStr.append("]");
        System.out.println(arrayStr);
    }
}