# Problem Statement
Design an algorithm that accepts a stream of integers and retrieves the product of the last `k` integers of the stream.
Implement the `ProductOfNumbers` class:
- `ProductOfNumbers()` Initializes the object with an empty stream.
- `void add(int num)` Appends the integer `num` to the stream.
- `int getProduct(int k)` Returns the product of the last `k` numbers in the current list. You can assume that always the current list has at least `k` numbers.
The test cases are generated so that, at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
## Constraints
- $0 <= \text{num} <= 100$
- $1 <= k <= 4 *10^4$
- At most $4 *10^4$ calls will be made to `add` and `getProduct`.
- The product of the stream at any point in time will fit in a **32-bit** integer.
# Solution
My solution is to use a [[Prefix Sum|prefix array]]. The array will be called `hist` and initialized to `[1]`. For each num we add, we append `num * hist[-1]`. Whenever we need to get the product of the last $k$ numbers, we divide `hist[-1]` (our current product sum) by the value at `hist[-(k+1)]`. Since the value we divide by is equal to the product of the numbers we aren't interested in, this removes their contribution to the current product sum.
> [!DANGER] Detail
> When we receive a zero as a number to add, I instead re-initialize `hist` to `[1]`, because if the last `k` numbers includes a zero, the answer will of course be `0`. Then we just need to add a check in our `getProduct` method to make sure `k` < `len(hist)` before returning, otherwise we return `0`.
```python
class ProductOfNumbers:
def __init__(self):
self.hist = [1]
def add(self, num: int) -> None:
if num == 0:
self.hist = [1]
return
self.hist.append(self.hist[-1]*num)
def getProduct(self, k: int) -> int:
if k < len(self.hist):
return self.hist[-1] // self.hist[-(k+1)]
return 0
```
Time Complexity: O$(n)$ | Space Complexity: O$(n)$