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}
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments