1352. Product of the Last K Numbers
Description
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 integernum
to the stream.int getProduct(int k)
Returns the product of the lastk
numbers in the current list. You can assume that always the current list has at leastk
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 ["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"] [[],[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.add(3); // [3] productOfNumbers.add(0); // [3,0] productOfNumbers.add(2); // [3,0,2] productOfNumbers.add(5); // [3,0,2,5] productOfNumbers.add(4); // [3,0,2,5,4] 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.add(8); // [3,0,2,5,4,8] 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 toadd
andgetProduct
. - The product of the stream at any point in time will fit in a 32-bit integer.
Solutions
Solution 1: Prefix Product
We initialize an array $s$, where $s[i]$ represents the product of the first $i$ numbers.
When calling add(num)
, we judge whether num
is $0$. If it is, we set $s$ to [1]
. Otherwise, we multiply the last element of $s$ by num
and add the result to the end of $s$.
When calling getProduct(k)
, we now judge whether the length of $s$ is less than or equal to $k$. If it is, we return $0$. Otherwise, we return the last element of $s$ divided by the $k + 1$th element from the end of $s$. That is, $s[-1] / s[-k - 1]$.
The time complexity is $O(1)$, and the space complexity is $O(n)$. Where $n$ is the number of times add
is called.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
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 |
|
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 30 |
|
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 30 |
|