Product of the Last K Numbers

Easy

0/40

Average time to solve is 15m

7 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

Sample Output 1:

20 40 0 32

Explanation for Sample Input 1:

After the first 5 insertions, the array will be [3 0 2 5 4]

Product with k=2 is 5*4 = 20
Product with k=3 is 2*5*4 = 40
Product with k=4 is 0*2*5*4 = 0

Insert 8 : [ 3 0 2 5 4 8]
Product with k=2 is 4*8 = 32

Sample Input 2:

Sample Output 2:

24 2784 8468 0 0

Hint 1

Hint 2

We can just append elements according to the query.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(Q ^ 2), where Q is the number of queries.

There are Q queries and in each query, and on each query we are doing O(Q) operations for calculating the product.

Space Complexity

O(Q), where Q is the number of queries.

We are only using arrays of the size of Q, thus space complexity is O(Q).

(100% EXP penalty)

Product of the Last K Numbers

Console