(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;
}
suppose we add three binary numbers having 1 in the 0th bit then suppose we add the first and the second number then the resulting number result in 10, the 1 will get carried over to 1st bit leaving with 0 in the the 0th bit to which we add with the 1 of the third number. so we calculate the count of the 1’s which can be carried to the ith bit from i - 1 th bit by dp[i-1] / 2. suppose 6 numbers with 1 in 0th bit, we add first and second, third and fourth , fifth and sixth each resulting in 10, the 1 will get carried to the next bit leaving 0 in the 0th bit. so the number of 1’s that get carried is 6/2 = 3
its just simple binary addition.
At least mention it is a dynamic programming problem. Also it is mentioned as EASY. I don’t know how he came to that dp part. Really a headache.
Edit- the video tutorial I found was very easy and clears everything.
Are you clear about the prefix sum thing?
@psychik Sorry to tag you, what if i follow this approach
- At position i, count how many numbers have bit set to 1. let that count be c. Then it can contribute a 1 to each of the bit positions starting from i to i+length of© in binary. Rest is same as you have told–>the checking part.
Anyone else also if can help me I will be highly grateful
what’s wrong in my code please help me
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lli long long int
using namespace std;
void bitwise(vectorbrr)
{
lli x=brr[0];
for(lli i=0;i<brr.size();i++)
x=(x|brr[i]);
cout<<x<<endl;
}
void bitmasking(vectorarr,lli n)
{
lli tot=1<<n;
vectorbrr;
lli sum=0;
for(lli N=0;N<tot;N++)
{
for(lli i=0;i<n;i++){
lli f=1<<i;
if((N&f)!=0)
sum+=arr[i];
}
brr.push_back(sum);
sum=0;
}
bitwise(brr);
}
int main()
{
lli t;
cin>>t;
while(t–)
{
lli n;
cin>>n;
vectorarr;
for(lli i=0;i<n;i++)
{
lli x;
cin>>x;
arr.push_back(x);
}
bitmasking(arr,n);
}
}
getting wrong ans why ??
if you got this logic, please explain!!!
i don’t make it!!!
