Enter your Email Address:

Delivered by FeedBurner

To get posts delivered to your Email

11 August 2010

Puzzle - "Binary Addition"

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

13 comments:

உத்தண்டராமன் said...

a[n] ==> first array
b[n] ==> second array
c[n+1] ==> third array - result array

int carrybit=0;

for(int i=n-1;i>=0;i--)
{
int add =a[i]+b[i]+carrybit;

if(add >= 2)
{
c[i+1] =add-2;
bit =1;
}
else
{
c[i+1] = 1;
bit =0;
}
}
c[0] = carrybit;

Lakshmi Narayanan N said...

@Udan

Can it be done without the variable carry?

Yuvaraj N said...

A modification of Udhan's without using a separate var.

for (int i=n-1; i >= 0; i--)
{
int add = a[i] + b[i] + c[i+1];

if (add >= 2)
{
c[i + 1] = add - 2;
c[i] = 1;
}
else
{
c[i + 1] = add;
c[i] = 0;
}
}

Lakshmi Narayanan N said...

@Yuvaraj

Cool. now without an if..else block..

Yuvaraj N said...

for (int i = n - 1; i >= 0; i--)
{
int add = a[i] + b[i] + c[i + 1];
c[i + 1] = add % 2;
c[i] = add / 2;
}

Lakshmi Narayanan N said...

@Yuvaraj, @Udhan
Fantastic. Thanks for the answers. Keep visiting this space, planning to add more contents on algos/ds/math

உத்தண்டராமன் said...

Superb yuvi .

@Lakshmi
Thanks for posting such questions looking for the next one.

~Udhan

Sandy said...

@Udhan,

Very nice solution.. In ur 1st comment, in the else block, instead of c[i+1] = 1; it will be c[i+1] = add;.. a typo error..

@yuvi,
very compact solution

@Lakshmi,
It was such fun solving this. Keep posting more !!

Lakshmi Narayanan N said...

@all

One variation. Assume that the arrays are of unequal size. can you come up with a algorithm?

உத்தண்டராமன் said...

Easiest way would be adding zero's to the beginning of the smallest array and shift the contents of the same to the end :)

But its a costly action and worst case. Will think to get a better solution ..

Yuvaraj N said...

A very unelegant solution. Wanted to avoid if..else and got this.

int[] a = { 1, 0, 1 };
int[] b = { 1, 1, 1, 1 };

int m = a.Length;
int n = b.Length;
int size = ((m + n) + Math.Abs(m - n)) / 2;
size++;

int[] c = new int[size];

for (int i = 1; i < size; i++)
{
int includea = (2 * (m / i)) / ((m / i) + 1);
int includeb = (2 * (n / i)) / ((n / i) + 1);
int intermediateSum = includea * a[Math.Abs(m - i) % m] + includeb * b[Math.Abs(n - i) % n] + c[size - i];
c[size - i] = intermediateSum % 2;
c[size - i - 1] = intermediateSum / 2;
}

Lakshmi Narayanan N said...

@Yuvi

Good and creative one. I really liked the way you employed division rule of data types and using of Math function.

You have tried to avoid if statement however the computational time seems to take more because of more calculations. Assuming that we are adding array of unequal size, we don't really have control or we cant predict the size of bigger array. If the size of bigger array is relatively more, then, the above algorithm consume equal time even small array even though "include" of smaller array is going to be zero.

In this scenario, I feel that usage of "if" statement help us to save few (lot?) CPU cycles. Here is another implementation for unequal array with an "if" statement


public static int[] binaryAddVariationNoConditional(int [] bigger, int[] smaller) {

if(bigger == null || smaller == null) {
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]/2;
sum[sumIndex] = sum[sumIndex] % 2;
}

for(; biggerIndex >=0; biggerIndex--, sumIndex--) {
sum[sumIndex] = sum[sumIndex] + bigger[biggerIndex];
sum [sumIndex - 1] = sum[sumIndex]/2;
sum[sumIndex] = sum[sumIndex] % 2;
}

return sum;
}

Lakshmi Narayanan N said...

@all,

One final variation.

Can we modify above variation 1 to work for any base. Please read Variation 2 section in the post.

thanks everyone for reading thro' and sharing your knowledge.