HackerEarth Navi and Math problem solution

In this HackerEarth Navi and Math problem solution, Navi is a famous mathematician. He is working on Division, Multiplication, and Addition. He is in need of some hidden patterns to discover some new concepts. He is giving you a task to find that sub-sequence of an array that has the maximum P % mod value, where the value of the mod is given below. This sub-sequence should have at least 2 elements.

HackerEarth Navi and Math problem solution.

#include <bits/stdc++.h>

#define maxm 1e7

using namespace std;

long long power(long long base, long long exponent, long long modulus)
{
    long long result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}
long long mod = 1000000007;

int main()
{
    int t;
    cin >> t;
    assert(1 <= t && t <= 10);
    for (int tt = 1; tt <= t; tt++) {
        int n;
        cin >> n;
        assert(2 <= n && n <= 16);
        vector <long long int > a(n + 1);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            assert(1 <= a[i] && a[i] <= maxm);
        }
        int p = 1 << n;
        long long ans = INT_MIN;
        for (int i = 1; i < p; i++) {
            long long mul = 1;
            long long add = 0;
            int ctr = 0;
            for (int j = 0; j < n; j++) {
                if (i&1<<j) {
                    ctr++;
                    add = (add + a[j])%mod;
                    mul = (mul * a[j])%mod;
                }
            }
            if (ctr >= 2 ) {
                long long int temp = power(add, mod - 2, mod);
                temp = (temp*mul)%mod;
                ans = max(ans, temp);
            }
        }
        cout << "Case #" << tt << ": " << ans << endl;
    }
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define INF INT_MAX
#define pb push_back
#define mp make_pair
#define fill(x,v) memset(x,v,sizeof(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define pln(n) printf("%lldn",n)
#define sl(n) scanf("%lld",&n)
#define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define F first
#define S second
#define mod (ll)(1e9 + 7)
#define ll long long int
#define MAX 1000006

ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;} 
ll arr[MAX];
int main()
{
    ll val,t,n,calc,cnt,ans,i,j,v1,v2,vit;
    sl(t);
    rep(vit,t)
    {
        sl(n);
        rep(i,n)
            sl(arr[i]);
        calc=1<<n;
        ans=-mod*mod;
        rep(i,calc)
        {
            v1=1; v2=0; cnt=0;
            rep(j,n)
            {
                if(i&(1<<j))
                {
                    v1*=arr[j];
                    v1%=mod;
                    v2+=arr[j];
                    cnt++;
                }
            }
            if(cnt>=2)
            {
                v2=modpow(v2, mod-2, mod);
                v1*=v2;
                v1%=mod;
                ans=max(v1, ans);
            }
        }
        printf("Case #%lld: %lldn",vit+1,ans);
    }
    return 0;
}

coding problems solutions