CODEWITHSUNDEEP
java
Mike
Mike

Reputation: 91

The Sum of large Integers using Arrays

I am trying to write a program that sums up the total of two large numbers. I used two arrays for the numbers to sum up and the third array to store the result of the summation, But I am getting the wrong output, would you check?

Here is my method:

public static int [] sumBigInt(int [] A, int [] B, int n) 
    {
        int sumPerCol = 0;
        int carriedValue = 0;           
        int[] totalArray = new int[A.length + 1];           
        for(int i = A.length - 1; i >= 0; i--)
        {
            sumPerCol = A[i] + B[i] + carriedValue;             

            if( i == 0)
                totalArray[i] = carriedValue;

            else if(sumPerCol >= 10)
            {   
                carriedValue = sumPerCol / 10;
                totalArray[i] = sumPerCol % 10;
            }
            else
            {
                totalArray[i] = sumPerCol;
                carriedValue = 0;
            }
        }// end of for-Loop         
        return totalArray;      
    }

**** In main, I am not getting the correct output:

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        System.out.println(TwoTo_n(8));

        int[] arrayA = {6,9,4,6,9,1,8,9,3,5,6};
        int[] arrayB = {5,9,6,4,3,1,6,7,6,9,5};

        int[] arrayTest = new int[arrayA.length + 1];

        for (int i = 0; i < arrayTest.length; i++)
            arrayTest[i] = sumBigInt(arrayA, arrayB, 14)[i];

        for (int i = 0; i < arrayTest.length; i++)
            System.out.print(arrayTest[i] + " ");   
    }

Here is the output I get :
1 9 1 1 2 3 5 7 0 5 1 0

The output should be: 1 2 9 1 1 2 3 5 7 0 5 1 => now the digit in position 1 disappears :(

There is ONE digit missing; that digit should be added at position zero in my final array, but its not showing up.

Thank you

Upvotes: 1

Views: 2559

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726849

Your code is almost correct. In order to fix it, think what happens to carriedValue after you finish the loop:

  • When the loop ends, and carriedValue is zero, your program returns the correct value
  • When the loop ends, and carriedValue is one, the most significant digit of the result gets dropped.

All you need to do to fix this is to "shift" digit positions in your totalArray by one, and assign carriedValue to the top digit after the end of the loop:

for(int i = A.length - 1; i >= 0; i--) {
    sumPerCol = A[i] + B[i] + carriedValue;             
    if(sumPerCol >= 10) { 
        carriedValue = sumPerCol / 10;
        totalArray[i+1] = sumPerCol % 10;
    } else {
        totalArray[i+1] = sumPerCol;
        carriedValue = 0;
    }
}// end of for-Loop 
totalArray[0] = carriedValue;

Note the use of totalArray[i+1] in place of totalArray[i]. This is because your method automatically extends the number of significant digits by one. You could change this behavior by re-allocating the array and copying data into it only when carriedValue is non-zero.

Demo.

Upvotes: 2

Related Questions