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 of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
Submit your solution at: https://leetcode.com/problems/product-of-array-except-self/
Using Division O(n)
You could do it using bruteforce, which O(n^2), but this is not acceptable for large inputs. The description says not using division, but here is the idea just for demonstration purposes. We need to get the multiplication sum for all integers, and use it to divide the current number, very straightforward.
The special cases need to be handled for zero numbers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int sum = 1; // multiplication with zeros int sum2 = 1; // multiplication without zeros int zeros = 0; // how many zeros for (int i = 0; i < nums.size(); i ++) { sum *= nums[i]; if (nums[i] != 0) { sum2 *= nums[i]; } else { zeros ++; } } if (zeros == nums.size()) { sum2 = 0; // all numbers are zeros } vector<int> r; for (int i = 0; i < nums.size(); i ++) { if (nums[i] == 0) { if (zeros > 1) { r.push_back(0); } else { r.push_back(sum2); } } else { r.push_back(sum / nums[i]); } } return r; } }; |
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int sum = 1; // multiplication with zeros
int sum2 = 1; // multiplication without zeros
int zeros = 0; // how many zeros
for (int i = 0; i < nums.size(); i ++) {
sum *= nums[i];
if (nums[i] != 0) {
sum2 *= nums[i];
} else {
zeros ++;
}
}
if (zeros == nums.size()) {
sum2 = 0; // all numbers are zeros
}
vector<int> r;
for (int i = 0; i < nums.size(); i ++) {
if (nums[i] == 0) {
if (zeros > 1) {
r.push_back(0);
} else {
r.push_back(sum2);
}
} else {
r.push_back(sum / nums[i]);
}
}
return r;
}
};Left and Right
We don’t need divisions. We need to use the current number to separate into two groups: left and right. And the answer for that position is just the production of its left and right.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> left(n, 0); vector<int> right(n, 0); left[0] = nums[0]; // left sum of first number for (int i = 1; i < n; i ++) { left[i] = nums[i] * left[i - 1]; } right[n - 1] = nums[n - 1]; // right sum of the last number for (int j = n - 2; j >= 0; j --) { right[j] = nums[j] * right[j + 1]; } vector<int> r(n, 0); if (n > 1) { r[0] = right[1]; r[n - 1] = left[n - 2]; } for (int i = 1; i < n - 1; i ++) { // it equals to the left multiplies the right. r[i] = left[i - 1] * right[i + 1]; } return r; } }; |
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, 0);
vector<int> right(n, 0);
left[0] = nums[0]; // left sum of first number
for (int i = 1; i < n; i ++) {
left[i] = nums[i] * left[i - 1];
}
right[n - 1] = nums[n - 1]; // right sum of the last number
for (int j = n - 2; j >= 0; j --) {
right[j] = nums[j] * right[j + 1];
}
vector<int> r(n, 0);
if (n > 1) {
r[0] = right[1];
r[n - 1] = left[n - 2];
}
for (int i = 1; i < n - 1; i ++) {
// it equals to the left multiplies the right.
r[i] = left[i - 1] * right[i + 1];
}
return r;
}
};This is kind of Dynamic Programming where intermediate production results are kept and re-used.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C/C++ Coding Exercise - Find Two Single Numbers
Next Post: How to Merge Two Sorted Lists (Recursion and Iterative)?
