@psychik The Setter’s solution is blank. I think you forgot to put the solution.
Why use only 51 bits, I mean it should go until 60 in worst case right ??
30 bits should be enough as constraint is
<2^30
Is it failing for Task #0 ?
1 Like
I think it would be more intuitive if one knows how multiple binary numbers are added column wise, also dp[i] = the number of bits available at the i^{th} column (after all carries have been propagated till the i^{th} column from LSB) 
(1LL<<50)=1125899906842624
(1LL<<30)*1e5=107374182400000
if n=10^5 and all a[I] =2^30-1
sum of array = n*a[I]
approx 50bits will be needed for storing sum
1
6
2312 213 34 323 1231 2331
answer expected: 8191
1
5
1 1 1 1 1
answer expected: 7
its log2((2^30)*(10^5))=46.6096404744 ~ 47, so he approximated to 50
How are we checking all the above said combinations to see if the i-th bit is set?
@girishgarg See below answer by @wait_and_watch where he states why 50 bits are necessary
((1LL<<50) = 1125899906842624
(1LL<<30)*1e5 = 107374182400000),
Do you still think you can do it with 30 bits only?
LOL
I have modified the solution given by Darshan making it a little simpler in fact. But still I’m getting TLE. I have even used fast I/O. Someone please help.
#include<bits/stdc++.h>
using namespace std ;
#define int long long int
int32_t main(){
int t ;
cin >> t ;
while(t--){
int n , count , x ;
cin >> n ;
int a[n] , ans = 0 ;
for(int i=0;i<n;i++) cin >> a[i] ;
for(int j = 30 ; j >= 0 ; j--){
count = 0 , x = (1LL<<j) ;
for(int i = 0; i < n ; i++){
if(a[i]&x){
count++ ;
ans|=(count*x) ;
}
}
}
cout << ans << endl ;
}
return 0 ;
}
can anyone help me why this sol. getting WA ??
Please check my code-
#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef long long ll;
int32_t main() {
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
fast_io;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll sum=0;
ll* arr= new ll[n];
for(ll i=0;i<n;i++){
cin>>arr[i];
sum+=arr[i];
}
ll prevCount=0;
ll count=0;
ll* dp= new ll[31]();
ll ans=0;
for(ll i=0;i<=30;i++){
ll curr=pow(2, i);
count=0;
for(ll i=0;i<n;i++){
if(arr[i]&curr){
count++;
}
}
dp[i]=count+ (prevCount/2);
prevCount=dp[i];
if(dp[i]){
ans+=curr;
}
}
cout<<ans<<endl;
}
return 0;
}
It gives correct answers for the above mentioned test cases, but shows wrong answer for the first test case.
#include<bits/stdc++.h>
using namespace std ;
#define int long long int
int32_t main(){
int t ;
cin >> t ;
while(t–){
int n , x ;
cin >> n ;
int a[n] , ans = 0 , count=0 ;
for(int i = 0 ; i < n ; i++) cin >> a[i] ;
for(int j = 0 ; j <= 30 ; j++){
x = (1LL<<j) ;
for(int i = 0 ; i < n ; i++){
if(a[i]&x){
count++ ;
ans|=(count*x) ;
}
}
count>>=1 ;
}
cout << ans << endl ;
}
return 0 ;
}
some modification then it’s giving correct ans .
same is happening to me u have to replace (1<<mask) by (1LL<<mask) that will do it for u i guess it worked for me
1 Like
Still doesnot work
This is my code.
I find the sum of all elements in the array and perform bitwise OR on SUM and the MAXIMUM ELEMENT in the array.
The example case is giving the right answer but when submitted 0 test case passed.
Code Starts:-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t;
cin >> t;
while(t–){
ll n;
cin >> n;
ll a[n];
for(int i = 0; i<n; i++){
cin >> a[i];
}
ll sum = 0;
for(int i = 0; i<n; i++){
sum += a[i];
}
ll maxi = *max_element(a, a+n);
ll ans = maxi | sum;
cout << ans << endl;
}
return 0;
}