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

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]

    Reply
    1. Kerem Unal

      The problem definition restricts the use of division.

      Reply

Enclose codes in [code lang="C"] [/code] tags

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