Questin：
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].
Example:
A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}
思路：
可以使用迭代累计。把output[i]=a[i]左边的乘积 x a[i]右边的乘积，所以，我们可以分两个循环，第一次先把A[i]左边的乘积放在Output[i]中，第二次把A[i]右边的乘积算出来；也可以直接放在一个循环中，只不过需要同时计算左边的乘积和右边的乘积。（当然也可分开计算A[i]左边和右边的数据，这样容易理解！最后将左边和右边的相乘即可）
代码如下：
void Multiplication_Array(int A[], int OUTPUT[], int n) {
int left = ;
int right = ;
for (int i = ; i < n; i++)
OUTPUT[i] = ;
for (int i = ; i < n; i++) {
OUTPUT[i] *= left;
OUTPUT[n - - i] *= right;
left *= A[i];
right *= A[n - - i];
}
}
void Mutiplication_Array2()
{
int *X = new int[n];
int *Y = new int[n];
// Create X
X[0] = 1;
for(int i = 1; i < n; i++){
X[i] = X[i-1] * A[i-1];
}
// Create Y
Y[n-1] = 1;
for(int i = n-2; i >= 0; i--){
Y[i] = Y[i+1] * A[i+1];
}
// Create Out
for(int i = 0; i < n; i++){
out[i] = X[i] * Y[i];
}
// Delete X and Y
delete[] X;
delete[] Y;
}