sum of two arrays element wise?

Question

There is a problem in which two random integer arrays are given, in which numbers from 0 to 9 are present at every index (i.e. single digit integer is present at every index of both given arrays). I need to find the sum of the numbers represented by the input arrays and put the result in another array.

I believe everything is fine with my code as I execute it almost 50 to 60 times for different arrays. But when I submit it in my school's online judge it accepted only 4 test cases and rejected the other two. I can't figure out in which case it will give wrong output. Need a little help guys.

HERE IS MY CODE

public static int[] sumOfTwoArrays(int[] arr1, int[] arr2){
    int size1 = arr1.length;
    int size2 = arr2.length;
    int carry = 0,sum,s,r;
    if(size1 == size2) {
        int arr3[] = new int[size1+1];
        for(int i=arr1.length-1;i>=-1;i--) { 
            if(i==-1) {
                arr3[i+1] = carry;
                //System.out.println(i+1+" "+arr3[i+1]);
            } else {
                sum = arr1[i] + arr2[i];
                if(sum>9) {
                    s =sum;
                    r = s % 10;
                    arr3[i+1] = carry + r;
                    carry = 1;
                    //System.out.println(i+" "+arr3[i]);    
                } else {
                    if(sum==9 && carry==1) {
                        s =sum+carry;
                        r = s % 10;
                        arr3[i+1] = r;
                    } else {
                        arr3[i+1] = sum+carry;
                        carry=0; 
                    }
                    //System.out.println(i+" "+arr3[i]);
                }  
            }      
        }
        return arr3;
    } else if (size1>size2) {
       int arr3[] = new int[size1+1];
       int diff = arr1.length - arr2.length;
       for(int i=arr1.length-1;i>=-1;i--) {
           if(i==-1) {
               arr3[i+1] = carry;
           } else {
               if(i>=diff) {
                   sum = arr1[i] + arr2[i-diff];
                    if(sum>9) {
                        s =sum;
                        r = s % 10;
                        arr3[i+1] = carry + r;
                        carry = 1;
                    } else {
                        if(sum==9 && carry==1) {
                            s =sum+carry;
                            r = s % 10;
                            arr3[i+1] = r;
                        } else {
                            arr3[i+1] = sum+carry;
                            carry=0; 
                        }
                    } 
                }  // end of diff i
                else {
                   arr3[i+1] =  arr1[i];
                   carry = 0;
                }
            }      
        }
        return arr3;
    } else {
        int arr3[] = new int[size2+1];
        int diff = arr2.length - arr1.length;
        for(int i=arr2.length-1;i>=-1;i--) {
            if(i==-1) {
                arr3[i+1] = carry;
            } else {
                if(i>=diff) {
                    sum = arr2[i] + arr1[i-diff];
                    if(sum>9) {
                        s =sum;
                        r = s % 10;
                        arr3[i+1] = carry + r;
                        carry = 1;
                    } else {
                        if(sum==9 && carry==1) {
                            s =sum+carry;
                            r = s % 10;
                            arr3[i+1] = r;
                        } else {
                            arr3[i+1] = sum+carry;
                            carry=0; 
                        }
                    }  
                }  // end of diff i
                else {
                    arr3[i+1] =  arr2[i];
                    carry = 0;
                }
            }      
        }
        return arr3;
    }   
}

Sample input:

int[] arr1 = {8,5,3,9,6};
int[] arr2 = {3,3,3,3,3};

Sample output:

{1,1,8,7,2,9}

Sample input:

int[] arr1 = {8,5,3,9,6};
int[] arr2 = {1,0,5}; 

Sample output:

{0,8,5,5,0,1}

Answer 1

Well, I have this algorith based on Eran solution (was working to fixe the bug he since corrected), I will shared it since I use less arrays.

public static int[] sum(int[] arr1, int[] arr2){
    int carry = 0;
    int sum = 0;

    int len1 = arr1.length;
    int len2 = arr2.length;
    int len = Math.max(len1, len2);

    int arr3[] = new int[len + 1];

    for (int i = 1; i <= len; i++) {
        sum =
            (len1 - i >= 0 ? arr1[len1-i] : 0)
            + (len2 - i >= 0 ? arr2[len2-i] : 0)
            + carry;

        arr3[len-i+1] = sum%10;
        carry = sum/10;
    }
    arr3[0] = carry;

    return arr3;
}

The usage of ternary operator is still readable so I find this a good solution.

For a short explanation, we read the arrays from the end, using i to read from right to left but based on the length of the arrays. The ternary operation is used in case of different array size.

EDIT :

Your algorithm doesn't manage correctly the carry value with different sized array.

185 + 16 gives 101.

Simply because you set the values like :

arr3[i+1] =  arr1[i];

So you forgot the carry that could occurs in the last operation.

Answer 2

This code is way more complicated than it has to be, which increases the chances of it containing bugs hard to detect.

You don't have to implement the algorithm 3 times (based of whether the first array is smaller, larger or equal to the second array). You can implement it once for two equal sized arrays whose size is Math.max(arr1.length,arr2.length). That would eliminate 2/3 of your code.

int len = Math.max(arr1.length,arr2.length);
int[] arr11 = new int[len];
int[] arr22 = new int[len];
int arr3[] = new int[len+1];
for(int i=len-1;i>=-1;i--) {
    if (i>=len-arr1.length)
        arr11[i]=arr1[i-(len-arr1.length)];
    if (i>=len-arr2.length)
        arr22[i]=arr2[i-(len-arr2.length)];
    // now you can use arr11[i] and arr22[i] instead of arr1[i] and arr2[i]
    ...
}

Besides, instead of sum = arr1[i] + arr2[i]; I suggest you add the carry immediately - sum = arr11[i] + arr22[i] + carry;. Now you only have to check once whether sum > 9.

    if(i==-1) {
        arr3[i+1] = carry;
    } else {
        sum = arr11[i] + arr22[i] + carry;
        if(sum>9) {
            arr3[i+1] = sum % 10;
            carry = 1;
        } else {
            arr3[i+1] = sum;
            carry = 0;
        }
    }

Combining the two snippets, you'll get :

int carry = 0;
int sum = 0;
int len = Math.max(arr1.length,arr2.length);
int[] arr11 = new int[len];
int[] arr22 = new int[len];
int arr3[] = new int[len+1];
for(int i=len-1;i>=-1;i--) {
    if(i==-1) {
        arr3[i+1] = carry;
    } else {
        if (i>=len-arr1.length)
            arr11[i]=arr1[i-(len-arr1.length)];
        if (i>=len-arr2.length)
            arr22[i]=arr2[i-(len-arr2.length)];
        sum = arr11[i] + arr22[i] + carry;
        if(sum>9) {
            arr3[i+1] = sum % 10;
            carry = 1;
        } else {
            arr3[i+1] = sum;
            carry = 0;
        }
    }
}
return arr3;

EDIT :

I had a small bug. I was adding 0s in the least significant digits of the smaller array (which are the high indices) instead of the most significant bits (the low indices), which made the result wrong if the arrays had different lengths. I fixed it, though now the part that copies the elements from the original arrays to arr11 and arr22 is less readable.