hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Product of the Last K Numbers
Problem: Product of the Last K Numbers
Problem Link: www.codingninjas.com/codestudio/problems/product-of-the-last-k-numbers_1232651
Question Asked By: Samsung, Apple, Microsoft.
Approach:
Declared a vector numbers.
For each query type 0, just inserted the given number into numbers.
For each query type 1, multiplied K numbers from the back.
Inserted the multiplied value into a vector ans.
Returned ans.
Time and Space Complexity:
Time Complexity: O(Q X N), [ For Larger N, it can be possible to do with O(Q) complexity. Approach: Cumulative Multiplication. ]
Space Complexity: O(N)
Code [C++]
#include <bits/stdc++.h>
vector<int> solve( int q, vector<pair<int, int>> queries )
{
vector<int>numbers, ans;
for(int i=0; i<q; i++){
if(queries[i].first == 0){
numbers.push_back(queries[i].second);
}
else{
long long multi = 1;
int temp = 0;
for(int j=numbers.size()-1; j>=0 && temp < queries[i].second; j--){
multi = multi * (long long)numbers[j];
if(multi == 0) break;
temp++;
}
ans.push_back(multi);
}
}
return ans;
}