Product of the Last K Numbers
Problem
Design a class that consumes a stream of integers and answers queries about the most recent numbers. add(num) appends num (0 ≤ num ≤ 100) to the stream, and getProduct(k) returns the product of the last k numbers added. Every query is guaranteed to ask about at most as many numbers as the stream currently holds, and every answer fits in a 32-bit integer.
add(3), add(0), add(2), add(5), add(4), getProduct(2), getProduct(3), getProduct(4), add(8), getProduct(2)20, 40, 0, 32class ProductOfNumbers:
def __init__(self):
self.prefix = [1]
def add(self, num):
if num == 0:
self.prefix = [1]
else:
self.prefix.append(self.prefix[-1] * num)
def get_product(self, k):
if k >= len(self.prefix):
return 0
return self.prefix[-1] // self.prefix[-k - 1]class ProductOfNumbers {
constructor() {
this.prefix = [1];
}
add(num) {
if (num === 0) this.prefix = [1];
else this.prefix.push(this.prefix[this.prefix.length - 1] * num);
}
getProduct(k) {
const n = this.prefix.length;
if (k >= n) return 0;
return this.prefix[n - 1] / this.prefix[n - 1 - k];
}
}class ProductOfNumbers {
private List<Integer> prefix = new ArrayList<>(List.of(1));
public void add(int num) {
if (num == 0) {
prefix = new ArrayList<>(List.of(1));
} else {
prefix.add(prefix.get(prefix.size() - 1) * num);
}
}
public int getProduct(int k) {
int n = prefix.size();
if (k >= n) return 0;
return prefix.get(n - 1) / prefix.get(n - 1 - k);
}
}class ProductOfNumbers {
vector<int> prefix{1};
public:
void add(int num) {
if (num == 0) prefix = {1};
else prefix.push_back(prefix.back() * num);
}
int getProduct(int k) {
int n = prefix.size();
if (k >= n) return 0;
return prefix[n - 1] / prefix[n - 1 - k];
}
};Explanation
The naive approach multiplies the last k numbers on every query, which costs O(k) each time. The trick is the multiplicative cousin of prefix sums: keep a list of running prefix products, where prefix[i] is the product of the first i numbers seen. The product of the last k numbers is then a single division: prefix[n−1] / prefix[n−1−k] — everything before the window cancels out.
Zeros break that plan twice: a zero in the history would make later divisions divide by zero, and any window that contains a zero has product 0 anyway. Both problems share one fix — when add(0) arrives, throw the whole history away and reset prefix to [1]. Nothing of value is lost: every window crossing that zero is 0 by definition.
That reset also makes the query side trivial. After a reset, prefix holds one entry per number added since the zero (plus the sentinel). So if k ≥ len(prefix), the requested window must reach back across the zero and the answer is 0. The sentinel 1 at index 0 ensures that a window covering everything since the reset still has a divisor to anchor against.
Walk the default example: add(3) gives prefix = [1, 3], then add(0) resets to [1]. Adding 2, 5, 4 builds [1, 2, 10, 40]. Now getProduct(2) = 40/2 = 20 and getProduct(3) = 40/1 = 40, but getProduct(4) asks for 4 numbers when only 3 exist since the zero, so it returns 0. After add(8), prefix = [1, 2, 10, 40, 320] and getProduct(2) = 320/10 = 32.
Every operation is O(1): add is one multiply and an amortized append (or a reset), and getProduct is one comparison plus one division. Space is O(n) for the prefix list, which in practice only spans the numbers added since the most recent zero.