One Algorithm Problem and my solution (08/27/2014)

Problem: Given an array of N numbers A[0,…,N-1], output an array M[0, N-1,], so that M[i] is the multiplication of all numbers in A except A[i]. No Division is allowed.

Let’s rephrase this problem: so M[i] = A[0] * A[1] * … * A[i-1] * A[i+1] * A[i+2]*…* A[N-1]

so it consists two parts: one is the multiplication below A[i]:  A[0] * A[1] * … A[i-1]; one is above A[i] : A[i+1] * A[i+2] * … * A[N-1].

Approach 1:

If we know any multiplication from index p to index q, then the problem can be solved by multiplying two parts: index from 0 … i-1 and i+1… N-1.

Let’s assume the input is int A[N], output will be Output[N]

First, create a temp array temp[N][N] and init each value with 1.

Second, calculate the auxiliary array values.

for(int i = 0; i < N-1; i++)

{

temp[i][i] = A[i];

for(int j = i+1; j < N-1; j++)

{

temp[i][j] = temp[i][j-1] * A[j];

}

}

 

Output[0] = temp[1][N-1];

for(int i = 1; i < N-1; i++)

Output[i] = temp[0][i-1]* temp[i+1][N-1];

The space complexity here is O(N^2).

 

Approach 2:

A close look at the above approach would discover that, it is not necessary to create the entire temp[N][N]. Actually if only we can create temp[0][i-1] and temp[i+1][N-1], then we are good to go. so here it is:

int tempBelow[N], tempAbove[N];

init tempBelow[0…N-1] with value 1;

int p = 1;

for(int i = 0; i < N-1; i++)

{

tempBelow[i] = p;

p *= A[i];

}

init tempAbove[0…N-1] with value 1;

p = 1;

for(int i = N-1; i >= 0; i–)

{

tempAbove[i] = p;

p *= A[i];

}

for(int i = 0; i < N; i++)

{

Output[i] = tempBelow[i] * tempAbove[i];

}

The space complexity is: O(N);

 

Approach 3:

In fact, we can also move on without the auxiliary array tempAbove and tempBelow. We can carry on the accumulated multiplications carefully.

 

init Output[0…N-1] with value 1;

int p = 1;

for(int i = 0; i < N; i++)

{

Output[i] = p;

p *= A[i]

}

p = 1;

for(int i = N-1; i >= 0; i–)

{

Output[i] *= p;

p *= A[i];

}

The space complexity is now constant O(1).

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s