source: https://leetcode.com/problems/product-of-array-except-self/
C/C++ Solution to LeetCode problem 238. Product of Array Except Self.
Problem
Given an integer array nums
, return an array answer
such that answer[i]
is equal to the product of all the elements of nums
except nums[i]
.
The product of any prefix or suffix of nums
is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n)
time and without using the division operation.
Examples
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints
2 <= nums.length <= 105
-30 <= nums[i] <= 30
- The product of any prefix or suffix of
nums
is guaranteed to fit in a 32-bit integer.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int s = nums.size() - 1;
vector<int> sol(nums.size(), 1);
vector<int> tmp(nums.size(), 1);
for(int i=1; i<nums.size(); i+=1) {
int l = nums[i - 1];
int r = nums[(s - i) + 1];
sol[i] = sol[i-1]*l;
tmp[s-i] = tmp[(s-i) + 1] * r;
}
for(int i=0; i<nums.size(); i+=1)
sol[i] *= tmp[i];
return sol;
}
};