C++ Coding Exercise – Product of Array Except Self

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.)

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.

`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.

`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 ofDynamic Programming where intermediate production results are kept and re-used.

–EOF–

GD Star Rating