Jan 152013
 

Given an array of integers, create another array whose i‘th element contain the product of all the elements in original array except the i’th element in original array.
prod array_0

Method-1 (Wrong): b[i] = product / a[i]

The first attempt to answer this question is generally to take product of all the numbers and then divide the product by a[i] to get b[i].

void multiplyMat(int* a, int* b, int n)
{
    int prod = 1;
    for(int i=0;i<n;i++){
	      prod *= a[i];
    }

    for(int i=0;i<n;i++){
	      b[i] = prod/a[i];
    }
}

Try running this code for {0, 1, 2, 3, 4} and the code will crash at run-time (because of division by zero – a[0] is zerp, when the below statement is executed inside the for loop,

b[0] = prod/a[0];

It will crash. So, change the code to:

if(a[i] != 0)
    b[i] = prod / a[i];

Method-2 (Without using division operator).

The interviewer may ask you write code without using division operator and it should still take O(n) time and constant extra space.Here is the solution:

prod array
Algorithm:

1. Set all the elements in array b such that 
    b[i] = b[i-1] * a[i].
2. prod = 1;
3. for(i=n-1; i>0; i++)
        b[i] = b[i-1] * prod;
        prod = prod * a[i];

Code:

/**
 * i'th element of b will be product of all the elements of a except a[i]
 * a - Input Array
 * b - Result Array
 * n - Size of both the arrays
 */
void multiplyMat(int* a, int* b, int n)
{
    b[0] = a[0];
	for(int i=1;i<n-1;i++){
	      b[i] = b[i-1] * a[i];
    }

   int prod = 1;
   for(int i=n-1; i>0; i--){
	     b[i] = b[i-1] * prod;
	     prod *= a[i];
   }
   b[0] = prod;
}

  One Response to “Array of products except the current elements”

Comments (1)
  1. I think this should also work!!!

    void multiplyMat(int* a, int* b, int n)
    {
    for(int i=0;i<n;i++){
    for(int j=0; j<n; j++){
    if (i != j)
    b[i] *= a[j];
    }
    }
    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)