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.

19 comments so far

  1. Ben on

    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

  2. Fr0z3n on

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

  3. Ben on

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

  4. DarK on

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

  5. Gaurav on

    wtf!!!

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

  6. DarK on

    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 <

  7. Gaurav on

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

  8. Gaurav on

    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 :(

  9. Gaurav on

    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 &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

  10. Fr0z3n on

    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. Fr0z3n on

    Stay tuned! Another Algorithm Challenge is on its way 😉

  12. Gaurav on

    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)

  13. Fr0z3n on

    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.

  14. Gaurav on

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

  15. jodhpuriguy on

    good algo (and the problem itself too)!

  16. Sharath on

    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…

  17. Sharath on

    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…

  18. Andrew on

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

  19. pavan on

    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 😀


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: