🔥BEATS 💯 % 🎯 | O(1) |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
IntuitionThe problem requires maintaining a sequence of numbers and efficiently computing the product of the last k numbers.Key Observations:

Brute Force Appro
![image.png](https://assets.leetcode.com/users/images/d4105043-f67a-4e45-8c61-5055a20de2e3_1739533153.2458458.png)

---
![1000089250.png](https://assets.leetcode.com/users/images/a1e02fe3-6aa4-437a-9db1-dd80be0904ae_1739535203.817809.png)


---

# **Intuition**  
The problem requires maintaining a sequence of numbers and efficiently computing the product of the last `k` numbers.  

### **Key Observations:**  
1. **Brute Force Approach (Inefficient)**  
   - Storing all numbers in an array and computing the product each time leads to **O(k)** time complexity per query.  
   - This is inefficient for large `k` values.  

2. **Optimized Approach Using Prefix Product**  
   - Instead of storing all numbers, maintain a **prefix product list**.
   - This allows us to compute the product in **O(1)** time using division.  

3. **Handling Zeros**  
   - If a zero is added, the prefix product becomes invalid for previous elements.
   - Reset the list when a zero is encountered.  

---

# **Approach**  
1. **Maintain a prefix product list (`products`)**  
   - `products[i]` stores the product of all elements from index `0` to `i`.  

2. **Adding a number (`add(num)`)**  
   - If `num == 0`, reset the `products` list because all previous products become invalid.  
   - Otherwise, store `num * last product`.  

3. **Getting the product of last `k` numbers (`getProduct(k)`)**  
   - If `k > length of list`, return `0` (as a zero may have been encountered).  
   - Otherwise, use **prefix division formula**:  
     \[
     \frac{P[n-1]}{P[n-k-1]}
     \]  

---

# **Complexity Analysis**  
- **Time Complexity:**  
  - `add(num)`: **O(1)** (Appending to list).  
  - `getProduct(k)`: **O(1)** (Single division).  
  - **Overall: O(1) per operation**.  

- **Space Complexity:**  
  - **O(n)** (Stores prefix products).  

---


```dart []
class ProductOfNumbers {
  final List<int> products = [];

  ProductOfNumbers() {}

  void add(int num) {
    if (num == 0) {
      products.clear(); // Reset the list
    } else {
      products.add(num * (products.lastOrNull ?? 1));
    }
  }

  int getProduct(int k) {
    int n = products.length;
    if (n == 0 || k > n) return 0;
    if (k == n) return products.last;
    return products.last ~/ products[n - k - 1];
  }
}
```


```java []
import java.util.*;

class ProductOfNumbers {
    private List<Integer> products;

    public ProductOfNumbers() {
        products = new ArrayList<>();
    }

    public void add(int num) {
        if (num == 0) {
            products.clear();
        } else {
            products.add(num * (products.isEmpty() ? 1 : products.get(products.size() - 1)));
        }
    }

    public int getProduct(int k) {
        int n = products.size();
        if (n == 0 || k > n) return 0;
        if (k == n) return products.get(n - 1);
        return products.get(n - 1) / products.get(n - k - 1);
    }
}
```


```python []
class ProductOfNumbers:
    def __init__(self):
        self.products = []

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

    def getProduct(self, k: int) -> int:
        n = len(self.products)
        if n == 0 or k > n:
            return 0
        if k == n:
            return self.products[-1]
        return self.products[-1] // self.products[n - k - 1]
```


```cpp []
#include <vector>

class ProductOfNumbers {
private:
    std::vector<int> products;
    
public:
    ProductOfNumbers() {}

    void add(int num) {
        if (num == 0) {
            products.clear();
        } else {
            products.push_back(num * (products.empty() ? 1 : products.back()));
        }
    }

    int getProduct(int k) {
        int n = products.size();
        if (n == 0 || k > n) return 0;
        if (k == n) return products.back();
        return products.back() / products[n - k - 1];
    }
};
```


```javascript []
class ProductOfNumbers {
    constructor() {
        this.products = [];
    }

    add(num) {
        if (num === 0) {
            this.products = [];
        } else {
            this.products.push(num * (this.products.length > 0 ? this.products[this.products.length - 1] : 1));
        }
    }

    getProduct(k) {
        let n = this.products.length;
        if (n === 0 || k > n) return 0;
        if (k === n) return this.products[n - 1];
        return Math.floor(this.products[n - 1] / this.products[n - k - 1]);
    }
}
```

---

# **Summary**
| Language  | Time Complexity | Space Complexity |
|-----------|----------------|----------------|
| **Dart**  | **O(1) per operation** | **O(n)** |
| **Java**  | **O(1) per operation** | **O(n)** |
| **Python** | **O(1) per operation** | **O(n)** |
| **C++**   | **O(1) per operation** | **O(n)** |
| **JavaScript** | **O(1) per operation** | **O(n)** |

The **prefix product approach** makes operations highly efficient, with **constant time complexity** per query. 🚀

---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}


['Array', 'Math', 'C', 'Prefix Sum', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']