Algorithm
Problem Name: 238. Product of Array Except Self
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.
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
numsis guaranteed to fit in a 32-bit integer.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
int *x = malloc(numsSize * sizeof(int));
//assert(x);
int i, j, k;
x[0] = 1;
for (i = 1; i < numsSize; i ++) {
x[i] = x[i - 1] * nums[i - 1];
}
k = nums[numsSize - 1];
for (i = numsSize - 2; i >= 0; i --) {
x[i] = x[i] * k;
k *= nums[i];
}
*returnSize = numsSize;
return x;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int>res(nums.size(), 1);
for(int i = 1; i < nums.size(); i++)
res[i] = res[i-1] * nums[i-1];
int right = 1;
for(int i = nums.size() - 1; i >= 0; i--){
res[i] *= right;
right *= nums[i];
}
return res;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] ans = new int[nums.length];
int mul = 1;
for (int i = 0; i < nums.length; i++) {
ans[i] = mul;
mul *= nums[i];
}
mul = 1;
for (int i = nums.length - 1; i >= 0; i--) {
ans[i] *= mul;
mul *= nums[i];
}
return ans;
}
}
Input
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const productExceptSelf = function(nums) {
const zeroIdx = new Set();
const p = nums.reduce((ac, el, idx) => {
if (el === 0) {
zeroIdx.add(idx);
return ac;
} else {
return ac * el;
}
}, 1);
const res = [];
for (let i = 0; i < nums.length; i++) {
if (zeroIdx.size > 1) {
res.push(0);
} else if (zeroIdx.size === 1) {
res.push(i === [...zeroIdx.values()][0] ? p : 0);
} else {
res.push(p / nums[i]);
}
}
return res;
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
m, res = 1, []
for i in range(len(nums)):
res.append(m)
m *= nums[i]
m = 1
for i in range(len(nums)-1,-1,-1):
res[i] *= m
m *= nums[i]
return res
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0238_ProductOfArrayExceptSelf
{
public int[] ProductExceptSelf(int[] nums)
{
var result = new int[nums.Length];
result[0] = 1;
for (int i = 1; i < nums.Length; i++)
result[i] = result[i - 1] * nums[i - 1];
int rightSide = 1;
for (int i = nums.Length - 1; i >= 0; i--)
{
result[i] = result[i] * rightSide;
rightSide *= nums[i];
}
return result;
}
}
}
Input
Output