🔥 Beats 99.69% 🔥 | 🌟 Proof 🌟 | ✔️ BruteForce + Optimal (PrefixProduct) ✔️ | 2 Solutions
Approach 1 : Brute Force O(k)IntuitionThe goal of the ProductOfNumbers class is to store a sequence of numbers and efficiently compute the product of the last k
---
# Approach 1 : Brute Force O(k)
---

# Intuition
The goal of the `ProductOfNumbers` class is to store a **sequence of numbers** and efficiently compute the product of the **last** `k` elements added.The `add(num)` function stores numbers in a **list**. The `getProduct(k)` function calculates the **product of the last** `k` elements from the list. If `k` is > the size of the list, it returns `0`.

# Approach
`Step 1` **Initialize the Class**
- Create an `ArrayList` | `vector` to store numbers.

`Step 2` **Implement add(num)**
- Append `num` to the list.

`Step 3` **Implement getProduct(k)**
- Check Edge Case If `k > list.size()`, return `0`.
- Iterate Over Last `k` Elements: Compute the product of the **last k elements using a loop**.
- Return the **Product**.

# Complexity
- Time complexity : $$O(k)$$
- Space complexity : $$O(1)$$

# Code

```Java []
class ProductOfNumbers
{
    // Step 1: Declare an ArrayList to store numbers.
    ArrayList<Integer> list; 

    public ProductOfNumbers()
    {   
        // Step 2: Initialize the ArrayList.
        list = new ArrayList<>(); 
    }

    public void add(int num)
    {
        // Step 3: Append the given number to the list.
        list.add(num); 
    }

    public int getProduct(int k)
    {
        // Step 4: Check if k is greater than the list size.
        if (k > list.size())
        { 
            // Step 5: Return 0 if not enough elements exist.
            return 0; 
        }

        // Step 6: Initialize product as 1.
        int product = 1; 
        
        // Step 7: Loop through last k elements.
        for (int i = list.size() - k; i < list.size(); i++)
        { 
            // Step 8: Multiply each element to product.
            product *= list.get(i); 
        }
        
        // Step 9: Return the final product.
        return product; 
    }
}
```

``` C++ []
class ProductOfNumbers
{
    // Step 1: Declare a vector to store numbers.
    vector<int> list;

public:
    // Step 2: Constructor initializes the vector.
    ProductOfNumbers() { } 

    void add(int num)
    {
        // Step 3: Append the given number to the vector.
        list.push_back(num); 
    }

    int getProduct(int k)
    {
        // Step 4: Check if k is greater than the vector size.
        if (k > list.size())
        { 
            // Step 5: Return 0 if not enough elements exist.
            return 0;
        }

        // Step 6: Initialize product as 1.
        int product = 1;
        
        // Step 7: Loop through last k elements.
        for (int i = list.size() - k; i < list.size(); i++)
        { 
            // Step 8: Multiply each element to product.
            product *= list[i]; 
        }

        // Step 9: Return the final product.
        return product; 
    }
};
```

---
# Approach 2 : Optimal - Prefix Product O(1)
---

![image.png](https://assets.leetcode.com/users/images/dfee419d-bd6e-49c7-a643-167bd7b57a5c_1739503793.0084295.png)

---

# Intuition
This optimized approach uses `prefixProduct` to compute the **product** in `O(1)` time instead of `O(k)`.The `prefixProduct` list stores **cumulative products** of all **added numbers**.If `0` is added, the **prefix product** is reset because any product containing `0` is `0`. `getProduct(k)` divides the **last stored prefix** product by the prefix product `k` **steps back**.


# Approach
`Step 1` **Initialize the Class**
- Create an `ArrayList` | `vector` named `prefixProduct`.
- Initialize it with `1` to **simplify calculations**.

`Step 2` **Implement add(num)**
- If `num == 0`, reset `prefixProduct = [1]`.
- Otherwise, append `prefixProduct[last] * num`.

`Step 3` **Implement getProduct(k)**
- Get the size of `prefixProduct`.
- If `k >= size`, return `0`.
- Otherwise, return `prefixProduct[size - 1] / prefixProduct[size - 1 k]`.

# Complexity
- Time complexity : $$O(1)$$
- Space complexity : $$O(1)$$

# Code

```Java []
class ProductOfNumbers
{
    // Step 1: Declare an ArrayList to store prefix products.
    ArrayList<Integer> prefixProduct; 

    // Step 2: Initialize the ArrayList.
    public ProductOfNumbers()
    {
        prefixProduct = new ArrayList<>();
        prefixProduct.add(1);
    }

    public void add(int num)
    {
        // Step 3: If num is 0, reset prefixProduct.
        if (num == 0) { 
            prefixProduct.clear();
            prefixProduct.add(1); 
        } 
        else
        {
            // Step 4: Append last product multiplied by num.
            prefixProduct.add(prefixProduct.get(prefixProduct.size() - 1) * num);
        }
    }

    public int getProduct(int k)
    {
        int size = prefixProduct.size();

        // Step 5: If k is larger than size, return 0.
        if (k >= size)
        { 
            return 0;
        }

        // Step 6: Compute the product using prefix division.
        return prefixProduct.get(size - 1) / prefixProduct.get(size - 1 - k);
    }
}
```

``` C++ []
class ProductOfNumbers
{
    // Step 1: Declare a vector to store prefix products.
    vector<int> prefixProduct; 

public:
    ProductOfNumbers()
    {
        // Step 2: Initialize with 1 for easier calculations.
        prefixProduct.push_back(1);
    }

    void add(int num)
    {
        // Step 3: If num is 0, reset prefixProduct.
        if (num == 0)
        { 
            prefixProduct.clear(); 
            prefixProduct.push_back(1); 
        }
        else
        {
            // Step 4: Append last product multiplied by num.
            prefixProduct.push_back(prefixProduct.back() * num);
        }
    }

    int getProduct(int k)
    {
        int size = prefixProduct.size();

        // Step 5: If k is greater than size, return 0.
        if (k >= size)
        { 
            return 0;
        }

        // Step 6: Compute the product using prefix division.
        return prefixProduct[size - 1] / prefixProduct[size - 1 - k];
    }
};
```
['Array', 'Math', 'Binary Search', 'Design', 'Data Stream', 'Hash Function', 'Prefix Sum', 'C++', 'Java']