Skip to content

1352. Product of the Last K Numbers 👍

  • Time:
    • Constructor: $O(1)$
    • add(num: int): $O(1)$
    • getProduct(k: int): $O(1)$
  • Space: $O(|\texttt{add()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class ProductOfNumbers {
 public:
  ProductOfNumbers() : prefix{1} {}

  void add(int num) {
    if (num == 0)
      prefix = {1};
    else
      prefix.push_back(prefix.back() * num);
  }

  int getProduct(int k) {
    return k >= prefix.size() ? 0
                              : prefix.back() / prefix[prefix.size() - k - 1];
  }

 private:
  vector<int> prefix;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class ProductOfNumbers {
  public ProductOfNumbers() {
    prefix = new ArrayList<>(List.of(1));
  }

  public void add(int num) {
    if (num == 0)
      prefix = new ArrayList<>(List.of(1));
    else
      prefix.add(prefix.get(prefix.size() - 1) * num);
  }

  public int getProduct(int k) {
    return k >= prefix.size() ? 0
                              : prefix.get(prefix.size() - 1) / prefix.get(prefix.size() - k - 1);
  }

  private List<Integer> prefix = new ArrayList<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class ProductOfNumbers:
  def __init__(self):
    self.prefix = [1]

  def add(self, num: int) -> None:
    if num == 0:
      self.prefix = [1]
    else:
      self.prefix.append(self.prefix[-1] * num)

  def getProduct(self, k: int) -> int:
    return 0 if k >= len(self.prefix) else self.prefix[-1] // self.prefix[len(self.prefix) - k - 1]