Product of the Last K Numbers ใน C++ : หาผลคูณ K ตัวท้ายด้วย Prefix Product

ออกแบบ Class **ProductOfNumbers** รองรับ:

• add(int num): เพิ่มตัวเลขท้าย List
• getProduct(int k): คืนค่า **ผลคูณของ k ตัวท้าย** (รับประกันว่ามี ≥ k ตัว)

ตัวอย่าง

add(3)  -> [3]
add(0)  -> [3, 0]
add(2)  -> [3, 0, 2]
add(5)  -> [3, 0, 2, 5]
add(4)  -> [3, 0, 2, 5, 4]
getProduct(2) -> 5*4 = 20
getProduct(3) -> 2*5*4 = 40
getProduct(4) -> 0*2*5*4 = 0
add(8)  -> [3, 0, 2, 5, 4, 8]
getProduct(2) -> 4*8 = 32

แนวทาง: Prefix Product Array + Zero Handling

Maintain Array pref ที่ pref[i] = Product ของ Elements แรก i ตัว (1-indexed, pref[0]=1)

• Add(num):
  • ถ้า num == 0 -> **Reset**: pref = [1] (เพราะ Product ทุกอย่างที่ข้าม 0 = 0)
  • Else -> pref.push_back(pref.back() * num)
• GetProduct(k):
  • n = pref.size() (Current Length + 1)
  • ถ้า k > n-1 -> Return 0 (มี 0 อยู่ใน k ตัวท้าย)
  • Else -> Return pref[n-1] / pref[n-k-1]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class ProductOfNumbers {
public:
    vector<int> pref; // Prefix Products, pref[0] = 1

    ProductOfNumbers() {
        pref.push_back(1);
    }

    void add(int num) {
        if (num == 0) {
            pref.clear();
            pref.push_back(1); // Reset
        } else {
            pref.push_back(pref.back() * num);
        }
    }

    int getProduct(int k) {
        int n = pref.size();
        if (k > n - 1) return 0; // Crosses a zero
        return pref[n - 1] / pref[n - k - 1];
    }
};

Input / Output

Operations: add(3) add(0) add(2) add(5) add(4) getProduct(2) getProduct(3) getProduct(4) add(8) getProduct(2)
Output:   20 40 0 32

ความซับซ้อน (Complexity)

• Add: O(1) Amortized
• GetProduct: O(1)
• Space: O(N) — Prefix Array (Reset เมื่อเจอ 0)

จุดสำคัญ

• **Zero Reset** เป็น Key: Product ข้าม 0 = 0 เสมอ -> เริ่ม Prefix ใหม่หลัง 0
• Division ได้เพราะ Integers และ No Zero ใน Segment ปัจจุบัน
• ใช้ long long ถ้าผลคูณใหญ่ (Constraints ปกติ int พอ)

LeetCode 1352 ครับ