Jun 28, 2007 -- posted by TechMonk

## 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.

The solution is the first of the questions in the page

http://placementsindia.blogspot.com/2007/12/solutions-to-few-google-top-interview.html

Easier than what I anticipated.. lot at me 😀

Why can’t you just do this?:

function algorithm_challenge(int &X, int N, int &M)

{

// Initialize local variables.

int i = 0;

int product = 0;

// Compute base product.

for (i = 0; i < N; i++)

{

product += X[i];

}

`// Now compute M[i].`

for (i = 0; i < N; i++)

{

if (X[i] == 0)

{

M[i] = 0;

}

else

{

M[i] = product / X[i];

}

}

}

Here is my Soln…

m[0] = 1;

// Put cumulative products into M array...

for(i from 2 to n){

m[i] = m[i-1]*x[i];

}

// Start from back and compute the reverse cumulative products in a temp variable, and store the final product back into M array..

`temp = 1;`

for(i from n to 1){

m[i] = m[i] * temp;

temp = temp*x[i];

}

Like in the soln given, n + 2n = 3n multiplications.. but only one extra temp variable.. instead of two extra long arrays…

Lets try better.. I have a similar algo that reduces the space complexity to O(1).. here the space complexity is O(n).. to be exact, O(2n). Actually it is not that very different.. just a little tweaking to the soln here and there…

good algo (and the problem itself too)!

cool.

ok bond!

my mistake. 🙂

nice one!

I have added a code snippet here http://snippets.dzone.com/posts/show/4226

As you can see through the code snippet, my approach does a total of 3N multiplications, while others are doing N^2 mutiplications. Hence my approach is O(3N) or O(N).

Hope you get a better picture now.

hey frozen, i am really out of touch with algo and coding for some days,can you answer some questions for me:

1. What is the difference between Complexity (big O) and number of computations?

2. I understand that the solution you gave is O(N), but what I fail to understand is that the number of computations (assuming one multiplication to be one computation), is still same as Dark’s solution. Then how can it be claimed that this solution is better than Dark’s?

(Correct me if I am wrong and the questions that I ask may sound naive, but i really want to know, I dont understand language of wikipedia and all)

Stay tuned! Another Algorithm Challenge is on its way 😉

Well. I guess this wordpress blog is not friendly for us to ask for solutions in comments. Next time onwards I will think of some other method of accepting solutions.

Thanks for your efforts. Ben and Dark have suggested the approach which anyone would come up with on the first time but runtime being O(N^2)

I am not able to understand what Gaurav is suggesting, but i assume he is suggesting a different solution than what i had in my mind and which 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.

The solution has been added to the actual post.

Finally I know how to post it right!!

//Initializing

for (int i=0; i<N; i++)

{

temp[0][i] = X[i]; //Leaves of the tree

M[i] = 1;

}

//Forming the tree with pair wise multiplication

int j =1;

for (int t=1; t < =logN; t++)

{

j *= 2;

for ( int k=0; k < N/j; k++)

{

temp[t][k] = temp[t-1][2*k] * temp[t-1][2*(k+1)]

}

}

`//Multiplying one number from each level of tree for each element in the array M`

j = 0.5;

for (int t=logN; t > =0; t++)

{

j *=2;

for (int i=0; i < N; i++)

{

for (k=0; k < t; k++)

{

if ( i < ( k*j) && i > (k-2)*j)

{

M[i] *= temp[t][k]

}

}

}

}

I really need to learn HTML and revisit my datastructures 🙁

And I dont even know if this code is right

This is the code for above explanation

//Initializing

for (int i=0; i<N; i++)

{

temp[0][i] = X[i]; //Leaves of the tree

M[i] = 1;

}

//Forming the tree with pair wise multiplication

int j =1;

for (int t=1; t

I hope the idea is correct, I dont really know about the code.

form a tree structure by multiplying.

`I am sorry about shitting so much all over :(`

I dont know what is wrong.

Delete the crap comments. will post again, sometime

Gaurav you need to change the less than symbols to their html codes..

the html code is

& l t ;

type it without spaces

it gives <

wtf!!!

where did my comment go!

I worked an hour to write the code.

i hope this one works.. it will be O(N^2) working on faster solution

for (int i = 0; i < N; i++)

{

M[i]=1;

for(int j = 0; j < N; j++)

{

if (i==j) continue;

M[i] *= N[j];

}

}

Well, this is my last try. I’m going to change the less-than signs. You can delete my other posts. I feel bad

for (int i = 0; i < N; i++)

{

M[i] = X[(i + 1) % N];

for (int j = 0; j < i; j++)

M[i] *= X[j];

for (int j = i + 2; j < N; j++)

M[i] *= X[j];

}

Please complete your solution. You can put your code inside <code></code> tags.

This one definitely is a tough one for me. I love programming puzzles! Of course I don’t claim to be a algorithm god in any way, I just think they’re fun, but I couldn’t wrap my mind around how to do this faster than O(n^2). I can’t wait to see the answer! All I could think of was probably the most obvious, but I’ll share it anyway:

for (int i = 0; i