# 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.

Example:

Input
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

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

Explanation
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32

Constraints:

• `0 <= num <= 100`
• `1 <= k <= 4 * 104`
• At most `4 * 104` 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.

``````class ProductOfNumbers {
public:
ProductOfNumbers() {}

data.push_back(num);
}

int getProduct(int k) {
int n = data.size(), res = 1;
for (int i = 0; i < k; ++i) {
res *= data[n - 1 - i];
}
return res;
}

private:
vector<int> data;
};
``````

``````class ProductOfNumbers {
public:
ProductOfNumbers() {}

if (num == 0) {
zeros.push_back(data.size());
}
data.push_back(num);
}

int getProduct(int k) {
int n = data.size(), res = 1;
if (zeros.size() != 0 && zeros.back() >= n - k) return 0;
for (int i = 0; i < k; ++i) {
res *= data[n - 1 - i];
}
return res;
}

private:
vector<int> data, zeros;
};
``````

``````class ProductOfNumbers {
public:
ProductOfNumbers() {}

prod.push_back(1);
if (num == 1) return;
for (int &a : prod) a *= num;
}

int getProduct(int k) {
return prod[(int)prod.size() - k];
}

private:
vector<int> prod;
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1352

https://leetcode.com/problems/product-of-the-last-k-numbers/

https://leetcode.com/problems/product-of-the-last-k-numbers/solutions/510265/c-prefix-array/

https://leetcode.com/problems/product-of-the-last-k-numbers/solutions/510260/java-c-python-prefix-product/

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation