×

Search anything:

# Data Structure with insert and product of last K elements operations

#### Data Structures Algorithms prefix sum array Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have presented 2 designs for Data Structure with insert and product of last K elements operations. Both operations can be done in constant time O(1).

1. Problem Statement
2. Naive approach for new Data Structure
3. Optimal solution for new Data Structure

To practice more such similar problems of designing Data Structures, go through this article.

Prerequisite: Prefix Sum Array

Let us get started with Data Structure with insert and product of last K elements operations.

# Problem Statement

We have to design a Data Structure that support the following operations:

• Insert: to insert a new element E into the Data Structure
• ProductK: to return the product of the last K elements inserted

The given input list be `[1, 2, 3, 4, 5, 6]`, and value for `k` is `3`

Therefore the product for last `k=3` elements is: result = 4 * 5 * 6 = 120

# Naive approach for new Data Structure

In this approach, we will use simple vector for storing list. The structure will be like this:

``````class data_structure{
vector<double> a;
int k;
}
``````

We will create two functions `insert(x)` to add elements and `product_of_k_ele()` to return of last `k` elements

insert(int x)

• this will just add elements in vector
• time complexity: `O(1)`

product_of_k_ele()

• this will calculate the product of last k elements simply by traversing last k elements.
• time complexity: `O(K)`

## Pseudo code

• declare empty container and two variables for storing value `k`.
• define function `insert(x)`
• insert element `x` in last
• define function `product_of_k_ele()`
• calculate product of last `k` elements by multiplying last k elements using linear traverse
• return calculated product

#### Code

``````#include<iostream>
#include<vector>
using namespace std;

class data_structure{
vector<double> a;
int k;

public:
// constructor for declaring variable k
data_structure(int x){
k=x;
}

// function for inserting elements in data structure
void insert(double x){
a.push_back(x);
}

// function for fetching product of last k elements
double product_of_k_ele(){
double product=1;
for(int i=a.size()-k; i<a.size(); i++) product*=a[i];
return product;
}
};

void solve()
{
// n = no of element data structure, k number of element from end
int n, k; cin>>n>>k;
data_structure ds(k);
int temp;
for(int i=1; i<=n; i++){
cin>>temp;
// inserting n elements in data structure
ds.insert((double) temp);
}
cout<<ds.product_of_k_ele()<<endl;
}

int main() {
solve();
return 0;
}

``````

# Optimal solution for new Data Structure

The technique that is used here is sliding window technique in which we will take window of size `k`from end of list and return product of all elements within that sliding window

Here we have used vector to make or container flexible and well indexed

• as our AIM is to get product of last k elements, we have created two functions `insert(x)` to add element `x` to our data_structure and calculate the product of `k` elements, `product_of_k_ele()` to just `return product of last k elements`
• `insert(x)` function we will first we will insert element in our container and till the size of vector is less then `k` we will just multiply product with element that we are inserting
• and when the container size is equal to `k` then our sliding window of size `k` can be formed and the product of elements in sliding window will get stored in `product` variable
• Now when the size of our container is `k` and we add a new element then we need to shift our sliding window to right by `1` as we want the product of last `k` elements or product of the last sliding window of size `k`. We need to only visualize sliding window and for calculating product of last sliding window we can just `multiply newly inserted element` with `product` and for removing contribution of last element we can just `divide product` with the `element which we have to remove from sliding window`

Ex: let `k=2`(size of sliding window) or our data structure
and we want to insert 4 elements

1. insert `a` in ds then `product = a`, `container = [a]`
2. insert `b` in ds then `product = a*b`, `container = [(a b)]`
3. insert `c` in ds then `product = (a*b*c)/a= b*c`, `container = [a (b c)]`
4. insert `d` in ds then `product = (b*c*d)/b= c*d`, `container = [a b (c d)]`

our result will be `c*d`

`Note:` `()` in container is representing sliding window

by this we can clearly see that for maintaining the product of last `k` element using this technique we can easily calculate product in `O(1)` at the time of insertion.

The structure of our new Data Structure will be:

``````class data_structure {
vector<double> a;
int k;
double product;
}
``````

### Example:

• let the given array be `[1, 2, 3, 4, 5, 6]` of `size = 6` and let the value of `k = 3`.
• as `k = 3` then the size of sliding window will also be `3`
• now we will insert each element one by one and multiply product with those number till the vector size is less then `k`
• when vector size will be k then our first sliding window of size k will be `[1, 2, 3]` and the product of elements will be stored in product variables. therefore `product = 1*2*3`
• then of we insert new element then our new sliding window will be `[2, 3, 4]` then in product `1*2*3*4` will get stored, for removing contribution of element before the first element of sliding window we will divide product with that element
• therefore product will be `(1*2*3*4)/1 = 2*3*4`
• when we add next element that is 5
then new sliding window = `[3, 4, 5]` and product will be `2*3*4*5`
for removing contribution of element before first element of sliding window we will divide product with that element
• therefore `product = (2*3*4*5)/2 = 3*4*5`
• after inserting all elements we will get our last sliding window as `[4, 5, 6]` and `product = 4*5*6`
• product of last `k` element will get stored in product and we can fetch that using `product_of_k_ele()` function
• we only have to visualize sliding window and focus on product variable in which we are storing product elements of last sliding window of size `k` in our vector of container

### insert(int x)

• this will add element `x` in our data structure
• time complexity: `O(1)`
• also it will calculate product of `k` element at the time of insertion only which will take `O(1)` time

### product_of_k_ele()

• this function will return product of last `k` element
• time complexity: `O(1)`

### Pseudocode

• declare empty container and two variables for storing `product of k elements` and value `k`.
• define function `insert(x)`
• insert element `x` in last
• calculating product of last `k` elements and update variable for product of `k` element variable
• define function `product_of_k_ele()`
• return product of last `k` elements

### Code

``````// Part of iq.opengenus.org
#include<iostream>
#include<vector>
using namespace std;

class data_structure{
vector<double> a;
int k;
double product;

public:
// constructor for declaring variable k
data_structure(int x){
k=x;
}

// function for inserting elements in data structure
void insert(double x){
a.push_back(x);
if(a.size()==1) product=a;
else if(a.size()>k) product/=a[a.size()-k-1], product*=x;
else product*=x;
}

// function for fetching product of last k elements
double product_of_k_ele(){
return product;
}
};

void solve()
{
// n = no of element data structure, k number of element from end
int n, k; cin>>n>>k;
data_structure ds(k);
int temp;
for(int i=1; i<=n; i++){
cin>>temp;
// inserting n elements in data structure
ds.insert((double) temp);
}
cout<<ds.product_of_k_ele()<<endl;
}
int main() {
solve();
return 0;
}

``````

Input

``````6 3
1
2
3
4
5
6
``````

Output

``````120
``````

With this article at OpenGenus, you must have the complete idea of Data Structure with insert and product of last K elements operations. #### Vikram Shishupalsingh Bais

Vikram Shishupalsingh Bais is an Open source enthusiast, competitive programmer skilled in programming languages C++, Python, Java, C. He has been an Intern at OpenGenus.

Data Structure with insert and product of last K elements operations