17. Product Array Puzzle

The problem can be found at the following link: Problem Link

Problem Description

You are given an array arr[] of size n. Your task is to construct an array res[] such that res[i] is equal to the product of all the elements of arr[] except arr[i]. Return the resultant array res[]. Note: Each element in res[] lies within the 32-bit integer range.

Examples:

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

Input: arr[] = [12, 0] Output: [0, 12] Explanation: For i = 0, res[i] = 0. For i = 1, res[i] = 12.

Constraints:

• $2 <= arr.size() <= 10^5$

• -100 <= arr[i] <= 100

My Approach

1. Handling Zeroes: If the array contains:

   • More than one zero: Every element in res[] will be 0.

   • Exactly one zero: Only the position corresponding to the zero will have the product of all other non-zero elements, and the rest will be 0.

   • No zeroes: Use the total product of all elements and divide by the current element for each position in the result array.

2. Efficient Computation:

   • Iterate through the array once to calculate the total product of non-zero elements and the count of zeroes.

   • Build the result array in a second pass.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n), where n is the size of the array. The algorithm requires two linear traversals of the array.

• Expected Auxiliary Space Complexity: O(1), as the solution uses only a constant amount of additional space.

Code (C++)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& arr) {
        int n = arr.size(), product = 1, zeroCount = count(arr.begin(), arr.end(), 0);
        if (zeroCount > 1) return vector<int>(n, 0);
        for (int x : arr) if (x) product *= x;
        for (int i = 0; i < n; i++) arr[i] = zeroCount ? (arr[i] ? 0 : product) : product / arr[i];
        return arr;
    }
};

Code (Java)

class Solution {
    public static int[] productExceptSelf(int[] arr) {
        int n = arr.length, product = 1, zeroCount = 0;
        for (int x : arr) if (x == 0) zeroCount++; else product *= x;
        if (zeroCount > 1) return new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = zeroCount > 0 ? (arr[i] == 0 ? product : 0) : product / arr[i];
        return arr;
    }
}

Code (Python)

class Solution:
    def productExceptSelf(self, arr):
        product, zero_count = 1, arr.count(0)
        if zero_count > 1:
            return [0] * len(arr)
        for x in arr:
            if x != 0:
                product *= x
        return [product if x == 0 else 0 if zero_count else product // x for x in arr]

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count