Beats 100% | 🔥 Efficient Product Tracker Approach 💡 | Easiest Solution Ever | Algorithm Explained
Youtube🚀 Beats 100% | 🔥 Efficient Prefix Product Approach 💡 | Algorithm Explained🔼 Please Upvote🔼 Please Upvote🔼 Please Upvote🔼 Please Upvote💡 Problem Breakdown
# Youtube
https://youtu.be/4rYSoKH9x7Q

![prod.png](https://assets.leetcode.com/users/images/d9577be5-c099-4dcd-b2bb-fe0d0cd3d223_1739507513.647673.png)

---

# 🚀 **Beats 100% | 🔥 Efficient Prefix Product Approach 💡 | Algorithm Explained**

# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**

---

## **💡 Problem Breakdown**  
Design a class `ProductOfNumbers` that supports two operations:  
1. `add(num)`: Appends `num` to the list.  
2. `getProduct(k)`: Returns the product of the last `k` numbers.  

Handling zeros efficiently is crucial because multiplying by zero invalidates all previous products.  

---

### **Example**  
#### **Input:**  
```plaintext
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
```

#### **Output:**  
```plaintext
[null,null,null,null,null,null,20,40,0,null,32]
```

#### **Explanation:**  
- Add `3`: List becomes `[3]`.  
- Add `0`: Resets all products to handle zeros.  
- Add `2`: List becomes `[2]`.  
- Add `5`: List becomes `[2, 10]`.  
- Add `4`: List becomes `[2, 10, 40]`.  
- `getProduct(2)`: Returns `20` (product of last 2 elements `[5, 4]`).  
- `getProduct(3)`: Returns `40`.  
- `getProduct(4)`: Returns `0` due to zero.  
- Add `8`: List becomes `[8]`.  
- `getProduct(2)`: Returns `32`.  

---

## **📝 Game Plan**  

1️⃣ **Prefix Product:** Maintain cumulative product to efficiently get products of last `k` elements.  
2️⃣ **Handling Zeros:** Clear the list and reset product when zero is added.  
3️⃣ **Efficient Querying:** Avoid recalculating products by using prefix division.  

---

## **🚀 Code Implementations**  

### **🟢 Java Solution**
```java
class ProductOfNumbers {
    ArrayList<Integer> list = new ArrayList<>();
    int prod = 1;

    public ProductOfNumbers() {
        
    }
    
    public void add(int num) {
        if(num == 0){
            list = new ArrayList<>();
            prod = 1;
            return;
        }
        prod = prod * num;
        list.add(prod);
    }
    
    public int getProduct(int k) {
        if(list.size() < k) return 0;
        int ans = list.get(list.size() - 1);
        if(list.size() == k) return ans;
        return ans / list.get(list.size() - 1 - k);
    }
}
```

---

### **🔵 C++ Solution**
```cpp
class ProductOfNumbers {
public:
    vector<int> list;
    int prod = 1;

    ProductOfNumbers() {}

    void add(int num) {
        if (num == 0) {
            list.clear();
            prod = 1;
        } else {
            prod *= num;
            list.push_back(prod);
        }
    }

    int getProduct(int k) {
        if (list.size() < k) return 0;
        if (list.size() == k) return list.back();
        return list.back() / list[list.size() - k - 1];
    }
};

```

---

### **🟣 Python 3 Solution**
```python
class ProductOfNumbers:
    def __init__(self):
        self.list = []
        self.prod = 1

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

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

```

---

### **🟡 JavaScript Solution**
```javascript
var ProductOfNumbers = function() {
    this.list = [];
    this.prod = 1;
};

/** 
 * @param {number} num
 * @return {void}
 */
ProductOfNumbers.prototype.add = function(num) {
    if (num === 0) {
        this.list = [];
        this.prod = 1;
    } else {
        this.prod *= num;
        this.list.push(this.prod);
    }
};

/** 
 * @param {number} k
 * @return {number}
 */
ProductOfNumbers.prototype.getProduct = function(k) {
    if (this.list.length < k) return 0;
    if (this.list.length === k) return this.list[this.list.length - 1];
    return this.list[this.list.length - 1] / this.list[this.list.length - k - 1];
};

```

---

## **📊 Complexity Analysis**  
- **Time Complexity:** **O(1)** for both `add` and `getProduct`.  
- **Space Complexity:** **O(n)** due to storing cumulative products in the list.  

---

## **💡 Why This Approach Is Optimal?**  
✔️ **Constant-Time Queries:** No need to iterate through the list for each product calculation.  
✔️ **Zero Handling:** Efficiently handles zeros by resetting the list and cumulative product.  
✔️ **Minimal Memory Overhead:** Only stores cumulative products instead of all individual elements.  

---

# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**  

💡 **If this helped, don’t forget to upvote! 🚀🔥**  
['Array', 'Math', 'Design', 'C', 'Data Stream', 'Prefix Sum', 'C++', 'Java', 'Python3', 'JavaScript']