Multiplication of numbers

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n).

For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Example:
A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}

Since the complexity required is O(n), the obvious O(n^2) brute force solution is not good enough here. Since the brute force solution recompute the multiplication each time again and again, we can avoid this by storing the results temporarily in an array.

Let’s define array B where element B[i] = multiplication of numbers from A[0] to A[i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then, we scan the array A from right to left, and have a temporary variable called product which stores the multiplication from right to left so far. Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.

The above method requires only O(n) time but uses O(n) space. We have to trade memory for speed. Is there a better way? (i.e., runs in O(n) time but without extra space?)

Yes, actually the temporary table is not required. We can have two variables called left and right, each keeping track of the product of numbers multiplied from left->right and right->left. Could you see why this works without extra space?

VN:F [1.9.22_1171]
Rating: 4.5/5 (40 votes cast)
Multiplication of numbers, 4.5 out of 5 based on 40 ratings

15 thoughts on “Multiplication of numbers

  1. leinad

    OMG, why didn't you use the solution as simple as following:
    ALL = A[0] *A[1] *…A[n-1];
    OUTPUT[i] = ALL/A[i];

    VA:F [1.9.22_1171]
    -19
    1. Omar Mohammad Othman

      Even if this is allowed, leinad, your solution is not correct. If a single zero exists in the array, all the outputs will be zeroes in your solution (besides – worse – you’ll actually attempt to divide by zero). 1337c0d3r’s solution works in this case, I’ve tested it!

      VA:F [1.9.22_1171]
      +4
  2. 1337c0d3r

    leinad, good observation. Unfortunately, you are not allowed to use division.

    The question statement mentioned "Solve it without division operator and in O(n)."

    VA:F [1.9.22_1171]
    0
  3. Vols

    what do you think of following solution, similar but maybe easier to understand: [mitbbs]

    int p=1;
    for(int i=0;i=0;–i){
    OUTPUT[i]*=p;
    p*=A[i];
    }

    VA:F [1.9.22_1171]
    0
  4. Pingback: Some interesting Google interview problems | tanliboy

  5. Anuj Dhamija

    hey nice work. ur website is vey informative.
    i see problem with the solution presented above with left and right pointers. doesnt really do the intended operation. For example Output[0] and Output[n-1] are always 1. Output[1] = A[n-2] and Output[n-2] = A[2]

    VA:F [1.9.22_1171]
    0
  6. carl

    nice work! However, your solution is still o(n) space. You just save a copy of o(n) temp array by using the output array. How about just print the result without an output array?

    VA:F [1.9.22_1171]
    +1

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*