# 14.02.2025 [1352. Product of the Last K Numbers]
Running suffix product #medium #math #prefix_product
14.02.2025
1352. Product of the Last K Numbers medium blog post substack youtube
Join me on Telegram
Problem TLDR
Running suffix product #medium #math #prefix_product
Intuition
The brute-force is accepted.
Didn't found myself O(1) solution, just wasn't prepared to the math fact: prefix product can work for positive numbers.
Approach
edge case is
1for the initial product
Complexity
Time complexity: $$O(n^2)$$ for brute-force, O(n) for prefix-product
Space complexity: $$O(n)$$
Code
class ProductOfNumbers(): ArrayList<Int>() {
fun getProduct(k: Int) = takeLast(k).reduce(Int::times)
}
struct ProductOfNumbers(usize, Vec<i32>);
impl ProductOfNumbers {
fn new() -> Self { Self(0, vec![1]) }
fn add(&mut self, n: i32) {
if n > 0 { self.1.push(n * self.1[self.0]); self.0 += 1 }
else { self.0 = 0; self.1.resize(1, 0) }
}
fn get_product(&self, k: i32) -> i32 {
if k as usize > self.0 { 0 } else { self.1[self.0] / self.1[self.0 - k as usize] }
}
}
class ProductOfNumbers {
int c = 0; vector<int> p = {1};
public:
void add(int n) { n > 0 ? (p.push_back(n * p.back()), ++c) : (p.resize(1, 0), c = 0); }
int getProduct(int k) { return k > c ? 0 : p[c] / p[c - k]; }
};