Home Arrays An array puzzle

# An array puzzle

Question: 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].

Array 1: {4, 3, 2, 1, 2}

Output: {12, 16, 24, 48, 24}

Since the complexity required is O(n), the obvious O(n2) brute force solution is not good enough here. Since the brute force solution recomputes 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 array 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?
Here is an implementation of the algorithm that does not require any extra space:-

#include<stdio.h>

void array_multiplication(int A[], int OUTPUT[], int n)
{
// Initializing left and right
int left = 1;
int right = 1;

// Initialize the output array
int i = 0;
for (i = 0; i < n; i++)
OUTPUT[i] = 1;

for (i = 0; i < n; i++)
{
OUTPUT[i] *= left;
OUTPUT[n - 1 - i] *= right;

// The variable left stores the multiplication of
// all elements on the left
left *= A[i];

// The variable right stores the multiplication of
// all elements on the right
right *= A[n - 1 - i];
}
}

int main(void)
{

int arr[] = {4, 3, 2, 1, 2};

int OUTPUT[5] = {0};

array_multiplication(arr, OUTPUT, 5);

int i = 0;
for(i=0; i<5; i++)
printf("%d ",OUTPUT[i]);

return 0;
}


Here is a running link of the above algorithm:- http://ideone.com/102tgS

#### You may also like

April 5, 2015 - 03:06

Or we just do as below?

In first for loop , find the product of all array numbers .

In the second for loop, A[i] = product/A[i]

April 6, 2015 - 13:36

The problem definition restricts the use of division.

April 6, 2015 - 15:24

Oh well. I didn’t notice it. Sorry ! Then this approach looks better ;)

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

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More