# Product of Array Exclude Itself

## Question

Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.

Example
For A=[1, 2, 3], return [6, 3, 2].


## 题解1 - 左右分治

### C++

class Solution {
public:
/**
* @param A: Given an integers array A
* @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
*/
vector<long long> productExcludeItself(vector<int> &nums) {
const int nums_size = nums.size();
vector<long long> result(nums_size, 1);
if (nums.empty() || nums_size == 1) {
return result;
}

vector<long long> left(nums_size, 1);
vector<long long> right(nums_size, 1);
for (int i = 1; i != nums_size; ++i) {
left[i] = left[i - 1] * nums[i - 1];
right[nums_size - i - 1] = right[nums_size - i] * nums[nums_size - i];
}
for (int i = 0; i != nums_size; ++i) {
result[i] = left[i] * right[i];
}

return result;
}
};


## 题解2 - 原地求积

### C++

class Solution {
public:
/**
* @param A: Given an integers array A
* @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
*/
vector<long long> productExcludeItself(vector<int> &nums) {
const int nums_size = nums.size();
vector<long long> result(nums_size, 1);

// solve the left part first
for (int i = 1; i < nums_size; ++i) {
result[i] = result[i - 1] * nums[i - 1];
}

// solve the right part
long long temp = 1;
for (int i = nums_size - 1; i >= 0; --i) {
result[i] *= temp;
temp *= nums[i];
}

return result;
}
};