Multiplication of numbers

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]右边的乘积算出来；也可以直接放在一个循环中，只不过需要同时计算左边的乘积和右边的乘积。

代码如下：

void Multiplication_Array(int A[], int OUTPUT[], int n) {
  int left = 1;
  int right = 1;
  for (int i = 0; i < n; i++)
      OUTPUT[i] = 1;
  for (int i = 0; i < n; i++) {
      OUTPUT[i] *= left;
      OUTPUT[n - 1 - i] *= right;
      left *= A[i];
      right *= A[n - 1 - i];
  }
}

Multiplication of numbers,布布扣,bubuko.com

Multiplication of numbers

原文：http://www.cnblogs.com/ywl925/p/3737008.html