CODEWITHSUNDEEP
algorithm
ChrisOdney
ChrisOdney

Reputation: 6384

Interview question on problem solving (arrays)

There is an array of integers, lets say 3,5,7,9. You are supposed to create another array and populate it such that the second array's 0th position should be a product of all numbers from the first array excluding the number at its 0th position, meaning it should be 5x7x9(excluding 3), number at the index 1 of the second array will be product of 3x7x9 (excluding 5).

The first answer that came up to my mind was having 2 for loops which will lead to a time complexity of O(n2). Later I figured this:

Multiplying all the numbers in the first array(3x5x7x9), and while populating the second array I will divide this product by the number at that position. divide by 3 if I am populating the 0th position, divide by 5 if I am populating the 1st position and so on. This would bring down the complexity from O(n2) to probably O(2n).

But the interviewer says division is not allowed. I could not think of anything else but storing the different possible multiples in some kind of a data structure and using it while populating. I gave up, but when asked for the answer he said he would maintain 2 arrays of forward and backward multiples. When asked about the space complexity issue of the solution, he said it could be optimized.

Upvotes: 12

Views: 4309

Answers (5)

Nemo
Nemo

Reputation: 71515

I think I can do it in O(n log n).

Store the product of the first half of the numbers and second half of the numbers.

Also store the product of the first quarter, second quarter, third quarter, and fourth quarter.

Also store the product of the first eighth, second eighth, ... 8th eighth.

And so on.

You can build this from the ground up by computing the product of each pair, then the product of each of those pairs, and so on.

Total amount of extra data here is O(n) and takes O(n) to compute (easy to show).

Now, to compute the output for (say) element 0, you take the product of the second half, the product of the second quarter (i.e., the second half of the first quarter), the product of the second half of the first eighth, etc., and multiply them together. There are log n such numbers, so this operation is log n.

To compute the product for element k, write k in binary and flip its bits. The high bit then tells you which half to start with; the next bit tells you which half of the remaining half to use next; the next bit tells you which half of the remaining quarter to use next; and so on.

So any output element can be calculated in log n time. Do that for each of the n output elements and you get O(n log n).

[edit]

Of course, the "forward and backward multiples" approach works, too. Guess I should read the question more carefully. :-)

[edit 2]

As for the interviewer's (and davin's) solution, you do not actually need to construct an extra array... Assuming you can edit the values in the output array.

First, construct the output array B such that B[i] = A[0]A[1]...*A[i-1] and B[0]=1. You can do this incrementally, so this is linear time:

B[0] = 1;
for (i=1 ; i < n ; ++i) {
    B[i] = B[i-1] * A[i];
}

Next, scan backwards from n-2 to compute the answers, keeping track of the "product so far":

x = A[n-1];
for (j=n-2 ; j >= 0 ; ++j) {
    B[j] *= x;
    x *= A[j];
}

This solves the problem in O(n) without building an extra array.

Upvotes: 2

davin
davin

Reputation: 45525

I'm not sure if the question is about the space or about the solution itself. Since everyone has been providing solutions it leads me to think they didn't understand the interviewer's solution, so here is an explanation:

We maintain two arrays. The first, the running product of the numbers of the original array. So the element at place i will be the product of the first i elements in the original array (no latex, but the ith entry has value it's pi{j=0 to i} j). And the second array is simply the reverse direction of that, so the ith entry will have value: pi{j=N-i to N} j.

To construct the final array required, we simply run along each of our two arrays and multiply entries. So the ith value in the final array, will be the product of all the entries, which is the product of 0 to i-1 times the product of i+1 to N, which is the product of the first array's i-1 entry and the second array's i+1 entry.

Total time and space O(n)

Upvotes: 9

Luka Rahne
Luka Rahne

Reputation: 10447

What about absuing Logarithm. Instead of dividing you subtract?

But if you can modify 1st array you could do somthing like

//pop arr2
r=1
for(i=len-1;i>=0;i--)
{
   r=r*arr1[i]
   arr2[i]=r
}

//modify arr1
r=1
for(i=0;i<len;i++)
{
   r=r*arr1[i]
   arr1[i]=r
}

//fix arr2
arr2[0]=arr2[1];
for(i=1;i<len-1;i--)
{
     arr2[i]=arr2[i+1]*arr1[i-1];
}
arr2[len-1]=arr1[len-2];

Upvotes: 1

Kevin L. Stern
Kevin L. Stern

Reputation: 375

I believe what he meant is that, given an array A={a_1, ..., a_n} he would create two new arrays:

F_A={a_1, a_1 * a_2, ..., a_1 * ... * a_n}

which can be constructed in linear time by maintaining a cumulative product while iterating forward over the array, and

B_A={a_1 * ... * a_n, ..., a_n * a_(n-1), a_n}

which can be constructed in linear time by maintaining a cumulative product while iterating in the reverse direction over the array.

Now, to populate index i in the result array you simply multiply F_A[i-1] with B_A[i+1]:

F_A[i-1] * B_A[i+1] = [a_1 * ... * a_(i-1)] * [a_(i+1) * ... * a_n]

Upvotes: 1

zw324
zw324

Reputation: 27180

  1. Store the elements 1 to i's product into an array A, with A[i] being the product of element 1 to element i;

  2. Store the elements i to n (size of input)'s product into an array B, with B[i] being the product of element i to element n;

  3. When result[i] is needed, use A[i-1]*B[i+1]. Corner cases are trivial this way, just use B[1] and A[n-2] (with A[n-1] being the last element).

Upvotes: 3

Related Questions