CODEWITHSUNDEEP
algorithmdata-structures
skyline0623
skyline0623

Reputation: 33

Optimal solutions for the practices about data structures from the Algorithm Design Manual

This question is from the book The Algorithm Design Manual, 3-28.
The question is:

You have an unordered array X of n integers. Find the array M containing n elements where M_i is the product of all integers in X except for X_i. You may not use division and can use extra memory. (Hint: There exists solution faster than O(n^2).

Anybody has some great ideas?

Upvotes: 3

Views: 277

Answers (2)

zangw
zangw

Reputation: 48366

Just use one array and two loops, one loop is from front to end, the other loop is from back to end.

b[0] =      a[1]*a[2]*a[3]*a[4]
b[1] = a[0]*     a[2]*a[3]*a[4]
b[2] = a[0]*a[1]*     a[3]*a[4]
b[3] = a[0]*a[1]*a[2]*     a[4]
b[4] = a[0]*a[1]*a[2]*a[3]

Here are the codes:

void solve(int arr[], int len){
    int index = 0;

    // loop from begin to end
    arr_b[0] = 1;
    for (index = 1; index < len; ++index){
        arr_b[index] = arr_b[index - 1]*arr_a[index - 1]; 
    }

    // loop from end to begin
    for (index = len-2; index > 0; --index){
        arr_b[0] *= arr_a[index + 1];
        arr_b[index] *= arr_b[0];
    }
    arr_b[0] *= arr_a[1];
}

Upvotes: 0

donatello
donatello

Reputation: 6235

O(n) solution:

  1. Compute array A such that A_i is the product of X_1..X_i
  2. Compute array B such that B_i is the product of X_i..X_n (in reverse, i.e. from array index n)
  3. Then compute M as M_i = A_(i-1)*B_(i+1)

Steps 1 and 2 can be computed in O(n) by using the subproducts computed in previous iterations.

[Of course, handle corner cases where the indices escape array bounds!]

Edit: I'm providing the complete solution below for clarity

  1. Compute array A as: A_1 = X_1; for i in (2..N): A_i = A_(i-1)*X_i
  2. Compute array B as: B_n = X_n; for i in (N..2): B_i = B_(i+1)*X_i
  3. Compute array M as: M_1 = B_2; M_n = A_(n-1); for i in (2..(N-1)): M_i = A_(i-1)*B_(i+1)

Upvotes: 4

Related Questions