<p>Design an algorithm that accepts a stream of integers and retrieves the product of the last <code>k</code> integers of the stream.</p>

<p>Implement the <code>ProductOfNumbers</code> class:</p>

<ul>
	<li><code>ProductOfNumbers()</code> Initializes the object with an empty stream.</li>
	<li><code>void add(int num)</code> Appends the integer <code>num</code> to the stream.</li>
	<li><code>int getProduct(int k)</code> Returns the product of the last <code>k</code> numbers in the current list. You can assume that always the current list has at least <code>k</code> numbers.</li>
</ul>

<p>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.</p>

<p>&nbsp;</p>
<p><strong class="example">Example:</strong></p>

<pre>
<strong>Input</strong>
[&quot;ProductOfNumbers&quot;,&quot;add&quot;,&quot;add&quot;,&quot;add&quot;,&quot;add&quot;,&quot;add&quot;,&quot;getProduct&quot;,&quot;getProduct&quot;,&quot;getProduct&quot;,&quot;add&quot;,&quot;getProduct&quot;]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

<strong>Output</strong>
[null,null,null,null,null,null,20,40,0,null,32]

<strong>Explanation</strong>
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 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= num &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= 4 * 10<sup>4</sup></code></li>
	<li>At most <code>4 * 10<sup>4</sup></code> calls will be made to <code>add</code> and <code>getProduct</code>.</li>
	<li>The product of the stream at any point in time will fit in a <strong>32-bit</strong> integer.</li>
</ul>

# Solution found from internet:
# https://algo.monster/liteproblems/1352

class ProductOfNumbers:
    def __init__(self):
        # Initialize a list with one element '1' to represent the prefix product
        self.prefix_products = [1]

    def add(self, num: int) -> None:
        # Adds the number to the sequence of numbers
        if num == 0:
            # If the number is zero, reset the list since any subsequent product will be zero
            self.prefix_products = [1]
        else:
            # Calculate the new product by multiplying the last product in the list with the new number
            self.prefix_products.append(self.prefix_products[-1] * num)

    def getProduct(self, k: int) -> int:
        # Returns the product of the last k numbers in the sequence
        if len(self.prefix_products) <= k:
            # If k is greater than or equal to the number of elements, the product is zero
            return 0
        else:
            # Otherwise, return the product of the last k numbers
            # by dividing the last prefix product by the product at (n-k-1)th position
            return self.prefix_products[-1] // self.prefix_products[-k - 1]


# Usage
# Initialize the object
obj = ProductOfNumbers()

# Add numbers with the add method
obj.add(3)  # Sequence is now: [3]
obj.add(0)  # Sequence is now: [1] because a zero resets everything
obj.add(2)  # Sequence is now: [1, 2]
obj.add(5)  # Sequence is now: [1, 2, 5]
obj.add(4)  # Sequence is now: [1, 2, 5, 4]

# Get the product of the last k numbers
print(obj.getProduct(2))  # Output: 20, since the product of last 2 numbers (5, 4) is 20
print(obj.getProduct(3))  # Output: 40, since the product of the last 3 numbers (2, 5, 4) is 40
print(obj.getProduct(4))  # Output: 0, since k>= the number of elements after the last reset (when 0 was added)

31600