See the original problem on HackerRank.
Solutions
The naive solution involves storing each number into the buffer and calculating the product when requested:


NaiveStreamingQualityAnalyzer::get
might be rewritten in terms on standard algorithms:


However, this solution proves to be excessively slow, resulting in a timeout for one test case. The issue lies in the fact that whenever a product operation is requested, the algorithm iterates through all the last K
elements to compute the product. The complexity of this approach is in the order of \(O(N \cdot K) \). We need to find a solution that does not involve calculating this product every time.
A more effective approach leverages the problem’s constraints and employs a classical pattern.
As per the problem statement, the product of any contiguous sequence of numbers can fit into a single 32bit integer without overflowing. Hence, it’s safe to compute the product during every add
operation. A pattern comes to the rescue: prefix sum. Indeed, we can maintain the running product of the elements rather than storing the elements themselves. This way, we can calculate the product of any subarray in constant time. In particular, the product of the last K
numbers is simply (pseudocode):


For example, suppose we have these numbers in the buffer:


Here is the running product:


The product of the last 2
elements (2 * 3 = 6
) is:


The product of the last 4
elements (2 * 4 * 2 * 3 = 48
) is:


The only problem with this approach is the presence of zeros: indeed, when the first 0 is added to the buffer, it perpetually sets the running product to zero. Instead, we can do the following trick: when a 0 is added, we empty and reset the buffer to the initial state. In this case, if a get
operation is requested, the algorithm will yield 0 as expected (because the last value added was 0). It will do it by checking the size of the current buffer against K
. In this regard, it’s practical to initialize the buffer as {1}
, this way both the running product and the check of the size would be simplified.
Here is the code:


Finally, get
is constant time and add
is “amortized constant” (if push_back
reallocates, it’s linear in the entire size, but chances decrease as the size increases).
In case HackerRank does not support ssize
yet, replace it with static_cast<int>(m_data.size())
.