Jun 28, 2007 posted by TechMonk 19

## Algortihm Challenge 1: No division!

I have decided to come up with series of challenges n problems which are algorithmic in nature and are asked in interviews of reputed companies like Microsoft, Google.

This one was asked in a Google interview recently. Try to answer it in your comments. I will post the solutions if no one comes up with the right answer (let’s hope not).

“You have an unordered array X of N integers. Find the array M containing N elements where M_i is the product of all integers in X except for X_i. You may not use division. You can use extra memory.

What is the best way of doing this?”

Example:

N=4

X = {2, 5, 3, 7}

M_0 = 5*3*7 = 105

M_1 = 2*3*7 = 42

M_2 = 2*5*7 = 70

M_3 = 2*5*3 = 30

M = {105, 42, 70, 30}

(hint: There are solutions faster than O(N^2))

**NOTE: while posting solution put your code (if any) inside <code></code> tags. **

**SOLUTION:**

Thanks for your efforts. The solution presented here runs in O(N) time. Yes O(N), and thats what an interviewer would expect you to come up with, in less than an hour.

Form two arrays P and Q such that

P[1] = 1

P[i] = X[1] * X[2] * … * X[i-1] for 1 < i <= N

and

Q[i] = X[i+1]*X[i+2]*… * X[N] for 1 <= i < N

Q[N] = 1

Set M[i] = P[i]*Q[i]

Both P and Q (i.e. M) can be found in O(N) time.

Once can access corresponding code snippet here.