How to find Largest triplet product in a stream in C ++
Hello Students, Today We are going to talk about how to find the largest triplet product in a stream in C++.
Implementing Largest Triple Product in a Stream in C++
We need to find the elements of the array first to compute from starting index to n-1. Now find the largest, second-largest, third-largest element of the array[0…i] and multiply them together. If index < 3 is found then print -1.
Examples:
Input : array[] = {1, 2, 3, 4, 5}
Output:
-1
-1
6
24
60
Explanation :
For index=0/1 only there are elements {1} / {1,2} ,so answer is -1 .
And For the case of index = 2, there are three elements {1, 2, 3} and multiplication of them is 6.
when index = 3 there are largest three elements {2, 3, 4} so the multiplication would be 24 and it continues gradually.
Algorithm for this problem
- Inserting the priority queue as the respective array element and the top element of that queue is largest so remove it and store the value with a denoted name.
- Now we are having the top as the second largest of the subarray so remove it again and store the value with a denoted name.
- Again we repeat the procedure as before storing the value with a denoted name.
- For the result print the values that we store earlier and reinsert the elements in the queue again.
C++ Code
// C++ implementation of largest triplet multiplication #include <bits/stdc++.h> using namespace std; void LargestTripletMultiplicationInaStream(int array[], int num) { priority_queue<int> queue; for (int i = 0; i < num; i++) { queue.push(array[i]); if (queue.size() < 3) cout << "-1" << endl; else { int x = queue.top(); queue.pop(); int y = queue.top(); queue.pop(); int z = queue.top(); queue.pop(); int result = x * y * z; cout << result << endl; queue.push(x); queue.push(y); queue.push(z); } } return; } // Main Function int main() { int array[] = { 1, 2, 3, 4, 5 }; int n = sizeof(array) / sizeof(array[0]); LargestTripletMultiplicationInaStream(array, n); return 0; }
Output :
-1 -1 12 84 252
Also read: C++ program for Density of Binary Tree in One Traversal
Leave a Reply