# Interview Questions

# Array of products except the current elements

- January 15, 2013
- Posted by: Kamal Rawat
- Category: Algorithms

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

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

}

}

}