1352. Product of the Last K Numbers

Daily 14/02/2025: [1352. Product of the Last K Numbers](https://leetcode.com/problems/product-of-the-last-k-numbers/description/?envType=daily-question&envId=2025-02-14) # 1. Tóm tắt đề bài Hãy thiết kế thuật toán sao cho nhận về một dòng dữ liệu số nguyên và có thể thu về tích của `k` số nguyên cuối cùng của dòng. Cụ thể hãy cài đặt lớp `ProductOfNumbers` như sau: - `ProductOfNumbers()`: khởi tạo đối tượng với một dòng dữ liệu trống. - `void add(int num)`: thêm số nguyên vào dòng. - `int getProduct(int k)`: Trả về tích `k` số nguyên cuối cùng của danh sách hiện tại. ### Giới hạn - $0 \le num \le 100$ - $1 \le k \le 4 * 10^4$ - Có nhiều nhất $4 * 10^4$ lời gọi hàm tới `add` và `getProduct`. - Tích của dòng dữ liệu tài thời điểm bất kỳ sẽ vừa với số nguyên 32 bit. - Dòng dữ liệu sẽ có ít nhất `k` phần tử # 2. Tóm tắt lời giải - Do cần lấy tích của một dãy số nguyên liên tiếp bất kỳ, ta có thể sử dụng kỹ thuật [prefix sum](https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/), nhưng thay vào đó là tích (so prefix product ig) - Tuy nhiên khi lấy tích thì có thể có giá trị bằng 0 nên cần phải xử lý. # 3. Lời giải chi tiết Với kỹ thuật prefix sum, ta có thể tìm tổng một subarray bất kỳ bằng cách lấy tổng từ đầu đến `r` trừ đi tổng từ vị trí từ đầu đến `l - 1` hay là `prefix[r] - prefix[l - 1]` với `r, l` là vị trí đầu và cuối của subarray (inclusive). Tương tự, với bài toán này, ta có thể lấy tích từ đầu đến cuối chia cho tích từ đầu đến số phần tử - `k`. Tuy nhiên, nếu có phần tử bằng 0 thì tích sẽ bằng 0 và sẽ không thể chia cho 0 được. Để giải quyết vấn đề này, ta có thể sử dụng một biến `streak` để đếm số phần tử liên tiếp khác 0 xuất hiện trong dòng. Tức là mỗi khi gặp phần tử khác 0 thì ta tăng biến `streak` lên 1 (increment), còn nếu gặp phần tử bằng 0 thì ta reset giá trị đó về 0. Có thể nhận thấy nếu `k > streak` thì tích sẽ bằng 0 do có phần tử bằng 0. Ngược lại, ta sẽ có tích của k phần tử cuối cùng của dòng sẽ bằng `prefix.back() / prefix[prefix.size() - 1 - k]`. Ngoài ra thay vì cộng tổng từ đầu đến phần tử hiện tại, nếu gặp phần tử 0 thì ta sẽ thêm một vào `prefix` thay vì nhân phần tử cuối với 0. Khi đó nếu thêm một phần tử khác 0 ngay sau đó thì tích sẽ bắt đầu với phần tử đó (hay là nhân với 1), và nếu `k == streak` thì dùng phép chia như trên thì sẽ đảm bảo chia với 1. [Lời giải tham khảo](https://leetcode.com/problems/product-of-the-last-k-numbers/submissions/1544983905/?envType=daily-question&envId=2025-02-14) ### Độ phức tạp Thời gian: $O(1)$ với mỗi lần gọi phương thức. Bộ nhớ mở rộng: $O(n)$ với $n$ là số phần tử trong dòng. # 4. Kết luận Đây là một bài toán khá tương tự vấn đề prefix sum nhưng việc lấy tích có thể bằng 0 khiến trở nên khá phức tạp. Tuy nhiên bằng một chút phân tích, ta có thể đưa ra cách xử lý phù hợp. Bài tập mở rộng: [974. Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/description/)