Product of the Last K Numbers
To implement the given requirements efficiently, we can make use of a prefix product approach. We maintain a list prefix_products
that stores the product of all the numbers we’ve seen till now in the stream. This helps in calculating the product of the last k
numbers in O(1) time.
Here’s how:
- For each number we add to the stream, multiply it with the last number in
prefix_products
and append it to the list. - To get the product of the last
k
numbers, we divide the last number inprefix_products
by the number inprefix_products
which is at indexlen(prefix_products) - k - 1
. This effectively gives the product of the lastk
numbers. Ifk
is equal to the size of the stream, we just return the last number inprefix_products
.
To handle the special case where the number is 0, if we add a 0 to the stream, we clear the prefix_products
list because multiplying any subsequent number by 0 would still be 0.
Here’s the implementation:
|
|
You can now create a ProductOfNumbers
object and call its methods as illustrated in the given example.