Given an array of n integers where n > 1,
nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].
Solve it without division and in O(n).
For example, given
[1,2,3,4], return [24,12,8,6].
Approach:
The idea is to traverse the array couple of times from left to right once and right to left once keeping track the accumulated product so far from both the sides.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ vector<int> productExceptSelf(vector<int> &nums) { int numsSize = nums.size(); vector<int> result(numsSize); int temp = 1; // stores the product on the left of each element excluding itself for(int i = 0; i < numsSize; i++){ result[i] = temp; temp = temp * nums[i]; } temp = 1; // stores the product on the left times product on right of each element excluding itself for(int i = numsSize - 1; i >= 0; i--){ result[i] = result[i] * temp; temp = temp * nums[i]; } return result; } |
