Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Bob and Beauty of the Array problem solution

YASH PAL, 31 July 2024
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("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

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes