# “A heisenbug (named after the Heisenberg Uncertainty Principle) is a computer bug that disappears or alters its characteristics when an attempt is made to study it.”

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

“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
P[i] = X * X * … * 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

### 19 Responses

1. pavan says:

The solution is the first of the questions in the page

Easier than what I anticipated.. lot at me 😀

2. Andrew says:

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

3. Sharath says:

Here is my Soln…

``` m = 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…

4. Sharath says:

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…

5. jodhpuriguy says:

good algo (and the problem itself too)!

6. Gaurav says:

cool.
ok bond!
my mistake. 🙂
nice one!

7. Fr0z3n says:

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.

8. Gaurav says:

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)

9. Fr0z3n says:

Stay tuned! Another Algorithm Challenge is on its way 😉

10. Fr0z3n says:

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.

11. Gaurav says:

Finally I know how to post it right!!

``` //Initializing for (int i=0; i<N; i++) { temp[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 &lt =logN; t++) { j *= 2; for ( int k=0; k &lt 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 &gt =0; t++) { j *=2; for (int i=0; i &lt N; i++) { for (k=0; k &lt t; k++) { if ( i &lt ( k*j) &amp&amp i &gt (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

12. Gaurav says:

This is the code for above explanation

``` //Initializing for (int i=0; i<N; i++) { temp[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 :(`

13. Gaurav says:

I dont know what is wrong.
Delete the crap comments. will post again, sometime

14. DarK says:

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 <

15. Gaurav says:

wtf!!!

where did my comment go!
I worked an hour to write the code.

16. DarK says:

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

17. Ben says:

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

18. Fr0z3n says:

19. Ben says: