Array of products except the current elements

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.


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:

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