🔥🔥🔥Beats 99.2%|💡Efficient and Easiest Solution Ever💡|Algorithm Explained 🚀🚀🚀
IntuitionThe problem requires retrieving the product of the last k elements efficiently after continuously adding numbers to the stream. A naive approach would
# Intuition
The problem requires retrieving the product of the last k elements efficiently after continuously adding numbers to the stream. A naive approach would involve storing all numbers and recalculating the product each time, leading to an inefficient solution. Instead, we maintain a prefix product array, which allows us to compute the product in constant time.
# Approach
We maintain a prefix product array, prod, where each element at index i represents the cumulative product of all elements from the start up to index i.

1. **When adding a number:** 
    - If num == 0, we reset the prefix product sequence and mark the position of the last zero.
    - If num ≠ 0, we append num * prod.back(), continuing the cumulative product.
2. **When retrieving the product of the last k elements:** 
    - If a zero exists within the last k elements, return 0 since multiplication by zero results in zero.
    - Otherwise, compute the product using prod[n - 1] / prod[n - k - 1], leveraging the prefix product property.

This approach ensures that both add(num) and getProduct(k) run efficiently.

# Complexity
- Time complexity:
    - add(num): O(1) (Constant time update to the prefix product list)
    - getProduct(k): O(1) (Constant time lookup and division)
- Space complexity: O(n) (We store a prefix product for all elements in the stream)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class ProductOfNumbers {
public:
    vector<int> prod; // Stores the prefix product sequence
    int lastzero = 0; // Stores the index of the last zero encountered
    int n = 0; // Stores the total number of elements added

    ProductOfNumbers() {
        prod.push_back(1); // Initialize prefix product with 1 (neutral multiplication identity)
        n++;
    }

    void add(int num) {
        if (num == 0) {
            // If the number is zero, reset prefix product tracking and store the zero's position
            prod.push_back(0);
            lastzero = n;
        } else if (prod[n - 1] == 0) {
            // If the last stored product is zero, start a new product sequence
            prod.push_back(num);
        } else {
            // Otherwise, multiply with the last prefix product to maintain the sequence
            prod.push_back(num * prod[n - 1]);
        }
        n++; // Increase the count of numbers added
    }

    int getProduct(int k) {
        // Check if a zero exists within the last 'k' numbers
        if ((n - k - 1) >= lastzero) {
            // If the prefix product before the range is zero, return the last product directly
            if (prod[n - k - 1] == 0)
                return prod[n - 1];
            else
                // Compute the product using division of prefix products
                return prod[n - 1] / prod[n - k - 1];
        } else {
            // If a zero exists in the last 'k' elements, the product is zero
            return 0;
        }
    }
};

```
# Input Breakdown
**Step-by-step Execution**

1. Initialize ProductOfNumbers

    ProductOfNumbers* obj = new ProductOfNumbers();

    Initializes prod = [1] (prefix product with 1 as identity).
    lastzero = 0, n = 1.

2. add(3)

    obj->add(3);

    Prefix product: 3 * 1 = 3
    prod = [1, 3]
    n = 2

3. add(0)

    obj->add(0);

    Since num = 0, reset prefix product sequence.
    Append 0, update lastzero = 2.
    prod = [1, 3, 0]
    n = 3

4. add(2)

    obj->add(2);

    Since the last product was 0, start a new product sequence.
    prod = [1, 3, 0, 2]
    n = 4

5. add(5)

    obj->add(5);

    prod = [1, 3, 0, 2, 10] (5 * 2)
    n = 5

6. add(4)

    obj->add(4);

    prod = [1, 3, 0, 2, 10, 40] (4 * 10)
    n = 6

7. getProduct(2)

    obj->getProduct(2);

    Computes product of last 2 elements ([5,4]).
    Formula: prod[n-1] / prod[n-k-1] = 40 / 10 = 4
    Output: 20

8. getProduct(3)

    obj->getProduct(3);

    Computes product of last 3 elements ([2,5,4]).
    Formula: prod[n-1] / prod[n-k-1] = 40 / 2 = 20
    Output: 40

9. getProduct(4)

    obj->getProduct(4);

    Last 4 elements include 0, so return 0.
    Output: 0

10. add(8)

    obj->add(8);

    prod = [1, 3, 0, 2, 10, 40, 320] (8 * 40)
    n = 7

11. getProduct(2)

    obj->getProduct(2);

    Computes product of last 2 elements ([4,8]).
    Formula: prod[n-1] / prod[n-k-1] = 320 / 40 = 8
    Output: 32

**Final Output**
[null, null, null, null, null, null, 20, 40, 0, null, 32]

# Key Observations

1. Handling 0: When a zero is added, the prefix product is reset, and products before it are ignored.
2. Fast Computation: Instead of recalculating the product, we use division for getProduct(k), achieving O(1) time complexity.
['Math', 'Prefix Sum', 'C++']