Last Updated: 11 Mar, 2021
Product of the Last K Numbers
Easy
Asked in companies
Given a sequence of queries of insertion and getProduct, you need to create an array using queries of type-0 and answer queries of type-1.
In each query, the input is of two types :
0 X: insert element ‘X’ at the end array.
1 K: find the product of the last 'K' elements in the array
Note:
For the query of type 1, you can assume that the array has at least k values. And at any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
Input Format:
The first line of the input contains ‘T’ denoting the number of test cases.
The first line of each test case contains ‘Q’ denoting the number of queries.
In the next Q lines input is either of the types :
0 X: insert element ‘X’ at the end array.
1 K: find the product of the last 'K' elements in the array.
Output Format:
For each test case, print a single line containing space-separated integers denoting answers of queries of type - 1.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 3
0 <= X <= 100
0 <= QUERIES <=5000
1 <= K <= 5000
Where X denotes the value to be stored in the array.
Time limit: 1 sec.
Approaches
- For type-0 query, we can just append elements at the end of the array.
- For type-1 query, we can take the product of last k elements in the array using for loop.
For type-0 query, we maintain a prefix array of products. We erase all the elements in our prefix array if we encounter a zero number for insertion. That makes sense because if we multiply zero with any of the suffix products, we will make the product zero. But, to make sure no overflow occurs, we append an additional 1 at the end of the array, since 1 is a multiplicative identity.
For type-1 query, we can take the product of last k elements via prefixes we are maintaining.
Algorithm for type-0:
- We create a prod array that stores products of prefixes.
- When we have to append ‘x’ into the array, we append x*prod[lastIndex], instead to maintain the suffix product array.
- If x = 0, we clear the prod array, because any suffix will result in 0 product.
- If the array is empty and we have to insert x, first we insert 1, then we insert x.
Algorithm for type-1:
- If the size of the prod array is less than equal k, the result is 0, as we might have cleared the array after encountering 0 before.
- Else we return prod[lastIndex]/prod[ lastIndex-k-1], which will give product of last k elements.
Prod[i] stores the product of the first i element.
Similar problems