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:

1. For each number we add to the stream, multiply it with the last number in prefix_products and append it to the list.
2. To get the product of the last k numbers, we divide the last number in prefix_products by the number in prefix_products which is at index len(prefix_products) - k - 1. This effectively gives the product of the last k numbers. If k is equal to the size of the stream, we just return the last number in prefix_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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class ProductOfNumbers:
    def __init__(self):
        self.prefix_products = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix_products = [1]  # reset the list
        else:
            self.prefix_products.append(self.prefix_products[-1] * num)

    def getProduct(self, k: int) -> int:
        # If k is greater than the size of the stream, it means there's a 0 in the last k numbers
        if k >= len(self.prefix_products):
            return 0
        
        # Return the product of the last k numbers
        return self.prefix_products[-1] // self.prefix_products[-k-1]

You can now create a ProductOfNumbers object and call its methods as illustrated in the given example.