There are two arrays of size "n". Each array represent a number in binary form meaning that each index has "0" or "1". Write an algorithm(program) to add both the array and store the result in the third array of size "n+1". This is an exercise in Coremen et al "Introduction to Algorithms".
Example:
array1 = {1, 0 , 1}
array2 = { 1, 0 , 0)
array3 = {1, 0, 0, 1}
Variation 1
As a next step, can you write an algorithm to handle input arrays of unequal size. For example, one array has "111" and another array has "10001". Find the binary sum for the arrays of unequal size.
Variation 2
Another variation is to generalize the above algorithm (Variation 1) for any base. In previous problem statements, we did it for binary. We need to make a generic algorithm that works for any base (even base 11, base 21 etc).
Example
array1 = { 1, 0, 1}
array2 = {1, 0, 0, 1}
array3 = {1, 1, 1, 0}
Answer (see comments on how we arrived at the solution)
public static int[] binaryAddVariationNoConditional(int [] bigger, int[] smaller, int base) {
if(bigger == null || smaller == null || base <= 1) {
throw new ArithmeticException("arguments passed is null.");
}
int max = Math.max(bigger.length, smaller.length);
int[] sum = new int[max + 1];
// Till now, bigger is not necessarily bigger. let us make it bigger
if(bigger.length < smaller.length) {
int[] temp = smaller;
smaller = bigger;
bigger = temp;
}
int biggerIndex = bigger.length - 1;
int smallerIndex = smaller.length - 1;
int sumIndex = sum.length - 1;
for(; smallerIndex >= 0; biggerIndex--, smallerIndex--, sumIndex--){
sum[sumIndex] = sum[sumIndex] + bigger[biggerIndex] + smaller[smallerIndex];
sum [sumIndex - 1] = sum[sumIndex]/base;
sum[sumIndex] = sum[sumIndex] % base;
}
for(; biggerIndex >=0; biggerIndex--, sumIndex--) {
sum[sumIndex] = sum[sumIndex] + bigger[biggerIndex];
sum [sumIndex - 1] = sum[sumIndex]/base;
sum[sumIndex] = sum[sumIndex] % base;
}
return sum;
}
