Ссылка на задачу – 1352. Product of the Last K Numbers.
📌 Описание задачи
Необходимо создать структуру ProductOfNumbers, которая:
- Позволяет добавлять числа в поток (
add(num)).
- Вычисляет произведение последних k чисел (
get_product(k)).
Гарантируется, что ответы не приведут к переполнению 32-битного целого.
💡 Идея
Будем использовать префиксные произведения.
Это позволит получать результат за O(1), выполняя деление последних значений.
Но так как деление на 0 запрещено, придётся аккуратно отслеживать этот случай и сбрасывать произведения при появлении нуля.
⚙️ Подход
- Используем
Vec<i64> для хранения префиксных произведений.
- Добавление числа:
- Если
num == 0, очищаем хранилище, так как любое произведение после нуля будет равно нулю.
- Иначе умножаем предыдущее произведение на текущее число и сохраняем результат.
- Вычисление
get_product(k):
- Если
k больше количества сохранённых чисел, возвращаем 0.
- Иначе делим последнее префиксное произведение на значение
k шагов назад.
⏳ Асимптотика
- Добавление:
O(1) ✅ (просто добавляем одно число)
- Получение произведения:
O(1) ✅ (одно деление)
- Память:
O(n) ✅ (храним только префиксные произведения)
📝 Исходный код
struct ProductOfNumbers {
prefix_products: Vec<i64>, // Stores cumulative product
}
impl ProductOfNumbers {
// Constructor initializes an empty product list
fn new() -> Self {
Self { prefix_products: Vec::new() }
}
// Adds a number, updating the prefix product
fn add(&mut self, num: i32) {
if num == 0 {
self.prefix_products.clear(); // Reset on zero
} else {
// Multiply the last stored product by the new number
let p = *self.prefix_products.last().unwrap_or(&1) * num as i64;
self.prefix_products.push(p);
}
}
// Returns the product of the last k numbers
fn get_product(&self, k: i32) -> i32 {
let k = k as usize;
if k > self.prefix_products.len() {
0 // Not enough numbers
} else {
let n = self.prefix_products.len();
// Compute product using division of prefix products
(self.prefix_products[n-1] / if k < n { self.prefix_products[n-k-1] } else { 1 }) as _
}
}
}
Tags: #rust #algorithms #prefixsum