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;
}