HackerEarth Monk and Multiplication problem solution

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.

#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("-1n");
            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("%lldn",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;
}

HackerEarth Monk and Multiplication problem solution.

Second solution

Leave a Reply