Skip to main content

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.

Solution Approach​

Expected Time Complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    vector<int> productExceptSelf(vector<int>& nums) {
        long long prod = 1;
        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i])
                prod *= nums[i];
            else
                cnt++;
        }
        if (cnt > 1) {
            nums.clear();
            nums.resize(n);
            return nums;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0)
                nums[i] = prod;
            else
                nums[i] = (prod * (cnt ^ 1)) / nums[i];
        }
        return nums;
    }
};