C++ Solution || O(k) -> O(1) || Both Approaches
IntuitionThe problem requires designing a data structure that allows adding numbers and retrieving the product of the last k numbers efficiently. The first appr
# Intuition
The problem requires designing a data structure that allows adding numbers and retrieving the product of the last `k` numbers efficiently. The first approach uses a simple vector to store numbers and computes the product directly when needed. The second approach optimizes this by maintaining a prefix product array to make queries faster.

# Approach 1: Brute Force Multiplication
## Explanation
- Maintain a vector `nums` to store added numbers.
- When querying for the product of the last `k` elements, iterate over the last `k` elements and compute the product manually.

## Complexity
- **Time Complexity:**
  - `add()`: **O(1)** (simply appending to a vector)
  - `getProduct(k)`: **O(k)** (iterating over the last `k` elements)
- **Space Complexity:** **O(n)** (storing all elements in the vector)

## Code
```cpp
class ProductOfNumbers {
public:
    vector<int> nums;
    int n;
    ProductOfNumbers() {
        nums.clear();
        n = 0;
    }

    void add(int num) { nums.push_back(num); }

    int getProduct(int k) {
        int n = nums.size();
        int prod = 1;
        for (int i = n - k; i < n; i++) {
            prod *= nums[i];
        }
        return prod;
    }
};
```

# Approach 2: Prefix Product Optimization
## Explanation
- Maintain a prefix product array `prod`.
- If `num == 0`, reset the array (since multiplication with zero invalidates prior products).
- Otherwise, maintain cumulative products to allow division-based retrieval in O(1) time.

## Complexity
- **Time Complexity:**
  - `add()`: **O(1)**
  - `getProduct(k)`: **O(1)**
- **Space Complexity:** **O(n)**

## Code
```cpp
class ProductOfNumbers {
public:
    vector<int> prod;
    int n;
    ProductOfNumbers() {
        prod.clear();
        n = 0;
    }

    void add(int num) {
        if (num == 0) {
            prod = {};
            n = 0;
        } else {
            if (prod.empty()) {
                prod.push_back(num);
            } else {
                prod.push_back(prod[n - 1] * num);
            }
            n++;
        }
    }

    int getProduct(int k) {
        if (k > n)
            return 0;
        else if (k == n)
            return prod[n - 1];
        return prod[n - 1] / prod[n - k - 1];
    }
};
```

## Summary
| Approach | `add()` Complexity | `getProduct(k)` Complexity | Space Complexity |
|----------|------------------|--------------------------|------------------|
| Brute Force Multiplication | O(1) | O(k) | O(n) |
| Prefix Product Optimization | O(1) | O(1) | O(n) |

The second approach is preferable as it significantly improves query time complexity from **O(k) to O(1)**.

![d3550b79-52c8-4704-846f-c00daecb5632_1737784461.667478.png](https://assets.leetcode.com/users/images/86145c28-cec6-4ee7-b975-d1abac140a17_1739512568.0833545.png)



['Array', 'Math', 'Design', 'Data Stream', 'Prefix Sum', 'C++']