Product of the Last K Numbers

class NumberMultiplier {
private:
    vector<int> cumulativeProduct;
    int currentSize = 0;
    
public:
    NumberMultiplier() {
        cumulativeProduct.push_back(1);
        currentSize = 0;
    }
    
    void addNumber(int value) {
        if (value == 0) {
            cumulativeProduct = {1};
            currentSize = 0;
        } else {
            cumulativeProduct.push_back(cumulativeProduct[currentSize] * value);
            currentSize++;
        }
    }
    
    int getProductOfLastK(int k) {
        if (k > currentSize) return 0;
        return cumulativeProduct[currentSize] / cumulativeProduct[currentSize - k];
    }
};

This solution involves a C++ class NumberMultiplier designed to efficiently compute the product of the last k numbers added to it. The class uses a private vector cumulativeProduct to store the cumulative products, allowing O(1) time complexity for retrieving the product of any last k elements. The implementation includes the following components:

• Constructor NumberMultiplier(): Initializes the cumulativeProduct with 1 and sets currentSize to 0. This setup helps handle the edge case when no numbers are added or the product of any numbers including zero should be zero.

• Method addNumber(int value): Adds a number to the stream. If the number is zero, it resets the cumulativeProduct and currentSize as any product including zero will result in zero. If not, it calculates the new cumulative product and adds it to cumulativeProduct, then increments currentSize.

• Method getProductOfLastK(int k): Retrieves the product of the last k numbers. It checks if k is greater than currentSize. If so, it returns 0, as there aren't enough numbers to form the product. If not, it computes the product by dividing the current cumulative product by the product at the position currentSize - k.

Use the addNumber method to add numbers to the buffer and the getProductOfLastK method to retrieve the product of the last k numbers dynamically and efficiently. This approach avoids direct product calculations, which could be inefficient and prone to integer overflows for large inputs.

class ProductStream {
    
    private ArrayList<Integer> productSeries = new ArrayList<>();
    private int currentSize = 0;
    
    public ProductStream() {
        productSeries.add(1);
        currentSize = 0;
    }
    
    public void append(int value) {
        if (value == 0) {
            productSeries = new ArrayList<Integer>();
            productSeries.add(1);
            currentSize = 0;
        } else {
            productSeries.add(productSeries.get(currentSize) * value);
            currentSize++;
        }
    }
    
    public int getLastKProduct(int k) {
        if (k > currentSize) return 0;
        return productSeries.get(currentSize) / productSeries.get(currentSize - k);
    }
}

The provided Java solution is a class named ProductStream that manages a series of products derived from a stream of numbers. Here's how it efficiently calculates the product of the last k numbers:

• Implement the ProductStream class with a private ArrayList<Integer> named productSeries to store cumulative products, and a currentSize variable to keep track of the size of the ArrayList.
• The constructor initializes productSeries by adding a 1 to handle multiplication effectively and sets currentSize to 0.
• The append(int value) method handles new numbers being added to the stream:
  • If the number is 0, it resets the productSeries as any number multiplied by zero is zero, affecting subsequent products. It reinitializes the list with 1 and resets currentSize to 0.
  • If the number is not zero, it appends a new product to productSeries by multiplying the latest value by the last number's cumulative product. It then increments currentSize.
• The getLastKProduct(int k) method returns the product of the last k entries:
  • If k is greater than currentSize, no sufficient numbers exist, hence it returns 0.
  • Otherwise, it calculates the product by dividing the most recent stored product by the product stored k places back in the list.

This efficient approach leverages cumulative multiplication to handle the up-to-date products which eliminates the need to multiply all k numbers each time, thus optimizing the operations when fetching the product of the last k numbers.

class NumberStreamProduct:
    def __init__(self):
        # Initialize buffer for products with 1 as the base value
        self.cumulative_products = [1]
        self.current_length = 0
    
    def append_value(self, value: int):
        # Handle special case where current value is 0
        if value == 0:
            self.cumulative_products = [1]
            self.current_length = 0
        else:
            # Record cumulative product of newly added value
            self.cumulative_products.append(self.cumulative_products[self.current_length] * value)
            self.current_length += 1
    
    def query_product(self, query_size: int) -> int:
        # Guard against invalid query sizes
        if query_size > self.current_length:
            return 0
        # Calculate the product by dividing the total product by the product before the desired range
        return (
            self.cumulative_products[self.current_length] // self.cumulative_products[self.current_length - query_size]
        )

The provided Python code defines a class NumberStreamProduct, which handles a sequence of numbers and allows the calculation of the product of the last k numbers efficiently. Here's how the implementation works:

• Initialization: The constructor initializes a list cumulative_products with a single element, 1, representing the cumulative product initialized at the base. current_length is set to 0, indicating the current length of the sequence processed.

• Appending Values:

  1. The append_value method adds a new value to the sequence.
  2. If the value is 0, it resets cumulative_products to [1] and current_length to 0 since any subsequent product containing this zero will be zero.
  3. For any non-zero value, it appends the product of this value and the last element of cumulative_products to cumulative_products. The current_length is incremented by one.

• Querying Product:

  1. The query_product method returns the product of the last k numbers.
  2. If the requested query_size is greater than current_length, it returns 0 as the query size is invalid (exceeds the number of elements in the sequence).
  3. Otherwise, it calculates the product by dividing the last entry in cumulative_products by the product recorded query_size elements earlier. This division effectively gives the product of the last k elements.

This approach is efficient as it avoids recalculating the product from scratch each time, utilizing previously stored results for optimal performance. The use of cumulative products facilitates quick computations, particularly useful when dealing with sequences where frequent product calculations are required.