Month: September 2013

I want to share a nice question that I came across on the internet. It doesn’t require knowledge of any algorithm so even beginners can attempt it.
There is an array of size n, a[n]. The objective is to construct another array of size n, lets call it b[n].
The array b should be such that b[i] (0<=i<n) contains the product of all elements of the array a, except the ith element (i.e. except a[i]).
For example, if array a is
4 3 5 1 10
then the array b will be
150 200 120 600 60
Simple, right? Here’s the catch: you cannot use the division operator. n can be very large, so your solution must be efficient enough to compute the array b in a reasonable amount of time. An O(n) solution would work.
Try it!

Algorithm #3: Greatest Common Divisor

I am going to cover a very simple algorithm this time. It is the GCD(Greatest Common Divisor) algorithm. The GCD of two numbers a and b is the greatest number c such that a%c==0 and b%c==0.

The naive algorithm to find the GCD of two numbers is something like this:

int GCD(int a, int b)
{
   int i=MIN(a,b);
   while(i>=1)
   {
      if(a%i==0 && b%i==0)
         break;
      i--;
   }
   return i;
}

Here we start from MIN(a,b) and find the highest number that is a factor of both a and b; and return it. Simple algorithm but not too efficient.

A better algorithm for finding the GCD of two numbers is theĀ Euclidean algorithm. The implementation is as follows:

int GCD(int a,int b)
 {
    if(a%b==0)
       return b;
    return GCD(b,a%b);
 }

This is a recursive algorithm. The function takes two numbers a and b. If b is a factor of a, then obviously the GCD of a and b is b. But if it is not, then the GCD of a and b is the GCD of b and a%b.

In other words, we take two numbers a and b and divide them. At each step, the remainder of the previous division becomes the divisor and the divisor of the previous division becomes the divident. We repeat this until the remainder becomes zero. The divisor when the remainder becomes zero is the GCD of a and b.

I’m sure most of you have done the Euclidean algorithm when you were in school. Maybe the image on this page will help refresh your memory:

http://f-of-x.blogspot.in/2010/04/euclids-algorithm-for-finding-gcf.html