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!

Advertisements

2 comments

    1. This can be done using dynamic programming.
      Use two extra arrays left[ ] and right[ ], both of size n
      The values stored in these arrays are as follows:
      left[i]= a[0] * a[1] * … * a[i-1] * a[i]
      right[i]=a[i] * a[i+1] * … * a[n-2] * a[n-1]
      Now array b[ ] can computed as follows:
      b[i]=left[i-1] * right[i+1]

      The code is:

      int i;
      left[0]=a[0];
      for(i=1;i<n;i++)
        left[i]=left[i-1]*a[i];
      
      right[n-1]=a[n-1];
      for(i=n-2;i>=0;i--)
        right[i]=right[i+1]*a[i];
      
      b[0]=right[1];
      for(i=1;i<n-1;i++)
        b[i]=left[i-1]*right[i+1];
      b[n-1]=left[n-2];
      

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s