In this HackerEarth Monk and Multiplication problem solution, The Monk learned about priority queues recently and asked his teacher for an interesting problem. So his teacher came up with a simple problem. He now has an integer array A. For each index i, he wants to find the product of the largest, second-largest, and third-largest integer in the range [1,i].


HackerEarth Monk and Multiplication problem solution


HackerEarth Monk and Multiplication problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
int main()
{
    freopen("Input.in", "r", stdin);
    freopen("Output.out", "w", stdout);
    int n,i;
    priority_queue<int>q;
    scanf("%d",&n);
    ll a[n];
    ll x,y,z;
    for(i = 0; i < n; i++) {
        scanf("%lld",&a[i]);
        q.push(a[i]);
        if(q.size() < 3) {
            printf("-1\n");
            continue;
        }
        x = q.top();
        q.pop();
        y = q.top();
        q.pop();
        z = q.top();
        q.pop();
        q.push(x);
        q.push(y);
        q.push(z);
        x = x*y;
        x = x*z;
        printf("%lld\n",x);
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
int arr [100005]; 
int main()
{
    ios_base::sync_with_stdio(0); 
    int N; cin >> N;
    assert (N>=1 and N<=100000); 
    for (int g=1; g<=N; g++)
    {
        cin >> arr[g]; 
        assert(arr[g]>=0 and arr[g]<=1000000); 
    }
    priority_queue <int> store; 
    for (int g=1; g<=N; g++)
    {
        if (g<=2)
        {
            cout << -1 << '\n'; 
            store.push(arr[g]); continue; 
        }
        store.push(arr[g]);
        int first = store.top();store.pop();
        int second = store.top();store.pop();
        int third = store.top();store.pop(); 
        store.push(first); store.push(second); store.push(third); 
        cout << 1LL*first*second*third << '\n'; 
    }//
    return 0;
}