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

 

1. 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.
2. 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.
3. Again we repeat the procedure as before storing the value with a denoted name.
4. 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