HackerEarth Bob and Beauty of the Array problem solution

In this HackerEarth Bob and Beauty of the Array problem solution, Bob is having an array of A of N elements. Bob wants to determine the beauty of the array and the beauty of the array is defined as:-

Determine Bitwise OR of maximum and minimum elements of every subset of size greater than or equal to 2 and add them. As the answer can be quite large, you have to report it by taking modulo with 1000000007.

HackerEarth Bob and Beauty of the Array problem solution.

#include<bits/stdc++.h>
using namespace std ;
#define pb push_back
#define mp make_pair
#define infile() freopen("in04.txt","r",stdin);
#define output() freopen("out04.txt","w",stdout);
#define ll long long
#define sc(t); scanf("%d",&t);
#define scl(t); scanf("%lld",&t);
#define sc2(n,m); scanf("%d%d",&n,&m);
#define scl2(n,m); scanf("%lld%lld",&n,&m);
#define debug(); printf("tusharn");
#define N 200005
#define mod 1000000007
#define printi(n) printf("%d",n);
#define inf ((1<<29)-1)
#define linf ((1LL<<60)-1)
const double eps = 1e-9;
set < ll > s ;
set  < int > si ;
set < ll > :: iterator it ;
vector < ll > v ;
vector < int > vi ;

int n,m,q,k ;
int a[N] ;
ll p2[N] = {0} ; 
ll ans = 0LL ; 
int hs[1002] = {0} ; 

ll power(ll x, ll y)
{
    ll res = 1;     
    x = x % mod;  
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;  
    }
    return res;
}


void func(int c1 , int cc ,  int con , ll val )
{
  int x = con; 
  int y = con + cc - 1 ; 
  ll tmp ; 
  if(x == 0)
  tmp = p2[y] ; 
  else
  tmp = (p2[y]-p2[x-1]+mod)%mod ; 
  tmp = (ll)(tmp*p2[c1-1])%mod ; 
  tmp = (ll)(tmp*val)%mod ; 
  ans = (ll)(ans + tmp)%mod ; 
return ; 
}
int main()
{
infile() ; 
output() ; 
int i , j , t ;
p2[0]=1LL; 
for(i=1;i<=200000;i++)
{
  p2[i]=p2[i-1]*2LL;
  p2[i]%=mod ;
}
for(i=1;i<=200000;i++)
{
  p2[i]=p2[i]+p2[i-1];
  p2[i]%=mod ; 
}
sc(n) ; 
for(i=1;i<=n;i++)
{
  scanf("%d",&a[i]) ; 
  hs[a[i]]++ ; 
}

for(ll i=1LL;i<=1000;i++)
{
  if(hs[i])
  {
    int cntuptonow = 0 ;
    // to get the contribution of all subsets having one unique element only.
    if(hs[i] >= 2)
    {
    ll tmp = power(2,hs[i]) ; 
    tmp = (tmp - (hs[i]+1) + mod)%mod ; 
    ans = (ll)(ans + tmp*i)%mod ; 
    ans%=mod ;  
    }
    for(j=i-1;j>=1;j--)
    {
      if(hs[j])
      {
          func(hs[i],hs[j],cntuptonow,(i|j)) ; 
          cntuptonow = cntuptonow + hs[j] ;           
      }
      //printf("i = %d j = %d ans = %lldn",i,j,ans) ; 
    }
  }
}
printf("%lldn",ans) ;
return 0 ;
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#include<limits>
#define ll long long

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define debugdec int deb=1;
#define debug() cout<<"real_flash>> "<<(deb++)
#define pb push_back
#define mk make_pair
#define MEM(a,b) memset(a,(b),sizeof(a))
#define TEST int test; cin >> test;while(test--)
#define si(x) scanf("%d",&x)
#define author real_flash
#define rep(p,q,r) for(int p=q;p<r;p++)
#define repr(p,q,r) for(int p=q;p>=r;p--)
#define repit(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define si2(x,y) scanf("%d %d",&x,&y)
#define si3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define FIND(x,y) x.find(y)==x.end()
#define sl(x) scanf("%lld",&x)
#define prl(x) printf("%lldn",x)
#define ff first
#define ss second
#define BE(a) a.begin(), a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define INF 111111111111111LL
#define mo 1000000007
#define PI 3.141592653589793

typedef pair<int, int > pii;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<ll, ll> pll;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a;}

//std::cout << std::setprecision(3) << std::fixed;
int MAX=numeric_limits<int>::max();
const int N=1e6+5;
//ios_base::sync_with_stdio(0);cin.tie(0);

int n,B=15;
ll a[N],po2[N],sp2[N],ans;
ll dig[20];
int mark[20];

int main()
{
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  //freopen("D:/progs/output.txt", "w", stdout);    
#endif
  po2[0]=1;
  rep(i,1,N)
  po2[i]=(po2[i-1]*2LL)%mo;
  sp2[0]=1;
  rep(i,1,N)
  sp2[i]=(sp2[i-1]+po2[i])%mo;
  
  si(n);
  assert(n>=1&&n<=2e5);
  rep(i,0,n)
  {
    sl(a[i]);
    assert(a[i]>=1&&a[i]<=1000);
  }
  sort(a,a+n);


  rep(i,0,B)
  {
    if((a[0]>>i)&1)
    {
      dig[i]=1;
    }
  }

  rep(i,1,n)
  {
    MEM(mark,0);
    rep(j,0,B)
    {
      if((a[i]>>j)&1)
      {
        ans=(ans+po2[j]*sp2[i-1])%mo;
        mark[j]=1;
      }
      else
      {
        ans=(ans+po2[j]*dig[j])%mo;
      }
    }
    rep(j,0,B)
    {
      dig[j]=(dig[j]*2LL)%mo;
    }
    rep(j,0,B)
    if(mark[j]==1)
      dig[j]=(dig[j]+1LL)%mo;
  }
  cout<<ans<<"n";

}

coding problems solutions