Best Practices for Data Structures from the Algorithm Design Guide
This question is from the Algorithm Design Guide, 3-28.
The question arises:
You have an unordered array X of n integers. Find an array M containing n elements, where M_i is the product of all integers in X except X_i. You cannot use division and you can use additional memory. (Hint: there is a faster solution than O (n ^ 2).
Anyone have any great ideas?
+3
source to share
2 answers
O (n) solution:
- Calculate array A such that A_i is the product of X_1..X_i
- Compute array B such that B_i is the product of X_i..X_n (in reverse order, that is, from array index n)
- Then calculate M as M_i = A_ (i-1) * B_ (i + 1)
Steps 1 and 2 can be computed in O (n) using the subproducts computed in previous iterations.
[Of course, handle corner cases where the indices are outside the array!]
Edit: I provide a complete solution below for clarity
- Calculate array A as: A_1 = X_1; for i in (2..N): A_i = A_ (i-1) * X_i
- Calculate array B as: B_n = X_n; for i in (N..2): B_i = B_ (i + 1) * X_i
- Calculate 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)
+4
source to share
Just use one array and two loops, one loop from start to end, another loop from start 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];
}
0
source to share