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?

1 2 3 4 5 6 7 8 9 10 11 12 |
void array_multiplication(int A[], int OUTPUT[], int n) { int left = 1; int right = 1; for (int i = 0; i < n; i++) OUTPUT[i] = 1; for (int i = 0; i < n; i++) { OUTPUT[i] *= left; OUTPUT[n - 1 - i] *= right; left *= A[i]; right *= A[n - 1 - i]; } } |

Multiplication of numbers,

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

-19Have you read the question carefully? Division is not allowed.

+2Even 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!

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

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

0Exactly, no division!

Plus, you may get overflowed if multiple all of them!

0what 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];

}

0above codes were cut half after 'posting'

-1Pingback: Some interesting Google interview problems | tanliboy

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]

0Output[0]=1 only until i=n-1. at that point, “right” will be carried all the way through to Output[0].

0if n == 0, the above code would just give us 1 as answer..

+2also for n == 1

0nice 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?

+1given o/p {4, 12, 24, 24, 48 }

looks wrong the correct o/p is 12 16 24 48 24

0It’s not the output. It’s the temporary product from A[0] to A[i].

0