[LeetCode] Product of the Last K Numbers

1352. Product of the Last K Numbers

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class ProductOfNumbers {
long long zero = INT_MAX;
vector<long long> prefixProduct {1ll};
public:
ProductOfNumbers() {}

void add(int num) {
if(!num) {
prefixProduct.clear();
prefixProduct.push_back(1ll);
zero = 1;
} else {
prefixProduct.push_back(num * prefixProduct.back());
zero++;
}
}

int getProduct(int k) {
if(k >= zero) return 0;
return prefixProduct.back() / prefixProduct[prefixProduct.size() - k - 1];
}
};

/**
* Your ProductOfNumbers object will be instantiated and called as such:
* ProductOfNumbers* obj = new ProductOfNumbers();
* obj->add(num);
* int param_2 = obj->getProduct(k);
*/
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/19/PS/LeetCode/product-of-the-last-k-numbers/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.