Product array puzzle

Given an array nums[], construct a Product Array nums[] such that nums[i] is equal to the product of all the elements of nums except nums[i].

Examples:

Input: nums[] = [10, 3, 5, 6, 2]
Output: [180, 600, 360, 300, 900]
Explanation: For i=0, P[i] = 3*5*6*2 = 180.
For i=1, P[i] = 10*5*6*2 = 600.
For i=2, P[i] = 10*3*6*2 = 360.
For i=3, P[i] = 10*3*5*2 = 300.
For i=4, P[i] = 10*3*5*6 = 900.

Input: nums[] = [12,0]
Output: [0, 12]

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

Constraints:
1 <= nums.size() <= 1000
0 <= nums[i] <= 200
nums[i] may contain duplicates.

Approach 01:

#include <vector>

class Solution {
public:
    std::vector<long long int> productExceptSelf(std::vector<long long int>& numbers) {
        int size = numbers.size();
        std::vector<long long int> result(size);
        long long int totalProduct = 1;
        int zeroCount = 0;

        // Calculate the total product of non-zero elements and count zeroes
        for (int i = 0; i < size; i++) {
            if (numbers[i] != 0)
                totalProduct *= numbers[i];
            else
                zeroCount++;
        }

        // If more than one zero, all elements in the result will be zero
        if (zeroCount > 1) {
            return std::vector<long long int>(size, 0);
        }

        // If exactly one zero, set the product only at the zero's position
        if (zeroCount == 1) {
            for (int i = 0; i < size; i++) {
                if (numbers[i] == 0)
                    result[i] = totalProduct;
                else
                    result[i] = 0;
            }
            return result;
        }

        // If no zeroes, compute the product except self for each element
        for (int i = 0; i < size; i++) {
            result[i] = totalProduct / numbers[i];
        }

        return result;
    }
};

from typing import List

class Solution:
    def productExceptSelf(self, numbers: List[int]) -> List[int]:
        size = len(numbers)
        result = [0] * size
        totalProduct = 1
        zeroCount = 0

        # Calculate the total product of non-zero elements and count zeroes
        for num in numbers:
            if num != 0:
                totalProduct *= num
            else:
                zeroCount += 1

        # If more than one zero, all elements in the result will be zero
        if zeroCount > 1:
            return [0] * size

        # If exactly one zero, set the product only at the zero's position
        if zeroCount == 1:
            for i in range(size):
                if numbers[i] == 0:
                    result[i] = totalProduct
                else:
                    result[i] = 0
            return result

        # If no zeroes, compute the product except self for each element
        for i in range(size):
            result[i] = totalProduct // numbers[i]

        return result

Time Complexity

• First Loop (Calculating Total Product and Counting Zeros):

  This loop iterates through all elements in the numbers vector once, taking \( O(n) \) time, where \( n \) is the number of elements in the vector.

• Second Loop (Handling Exactly One Zero):

  If there is exactly one zero, the function iterates through the numbers vector again to set the result values, which also takes \( O(n) \) time.

• Third Loop (Handling No Zeros):

  If there are no zeros, the function iterates through the numbers vector once more to compute the product except for each element, taking \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), as each loop iterates through the vector exactly once.

Space Complexity

• Auxiliary Space for Result Vector:

  The function creates a result vector of size n, which takes \( O(n) \) space.

• Auxiliary Variables:

  The function uses a constant amount of extra space for variables like totalProduct and zeroCount, which is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the space required for the result vector.