# An array puzzle

By | March 30, 2015

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 will be multiplication of A to A[N-1] and Output will be multiplication of A and from A 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 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 = {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 Author: nikoo28

a tech-savvy guy and a design buff...

## 3 thoughts on “An array puzzle”

1. arulsubramaniam

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]

1. Kerem Unal

The problem definition restricts the use of division.

1. arulsubramaniam

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.