Thursday, February 9, 2012

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;
    }
}

No comments:

Post a Comment

Please, before starting to comment, evaluate if what you want to write is useful, respectful and positive. A kid may read this also.

Give a good example!