Product of the Last K Numbers

Problem Id: 1352 Difficulty: Medium Tag: Array Tag: Design


Intuition

The product of the last K element could be calculated by the product of all the element divide the product of previous K - 1 elements.

Please note 0 should be handled differently, since there should be no 0 in the dividor. Once there is a 0, all the nodes previous than 0 would be useless. So once there is a new 0 added, we could re-initial the list and remove all previous nodes.

Solution


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

    def add(self, num: int) -> None:
        if num == 0:
            self.__init__()
        else:
            self.product *= num
            self.nums.append(self.product)

    def getProduct(self, k: int) -> int:
        n = len(self.nums) - 1
        if k > n:
            return 0
        prev = n - k
        return self.product // self.nums[prev]


# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)