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


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("tushar\n");
#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 = %lld\n",i,j,ans) ; 
    }
  }
}
printf("%lld\n",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("%lld\n",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";

}