include
include
include
include
include
include
include
include
define loop(x, s, e) for(int x=s; x<e; x++)
define bin(x) for(int i=63; i>-1; i–){\int t = (x&(1ll<<i))?1:0;\cout<<t;}\cout<<endl;
define int long long
define debn(x) cout<<x<<endl;
define deb(x) cout<<x;
using namespace std;
void solve(){
int n;
cin>>n;
int a[n], ored=0;
loop(i, 0, n){
cin>>a[i];
ored = ored|a[i];
}
// cout<<ored<<endl;
if((ored&1ll)==0){cout<<n;return;}
int count = 0;
loop(i, 0, 63){
if(ored&(1ll<<i)){
count++;
}
else break;
}
int threshold = pow(2,count)-1;
int remove = 0;
loop(i, 0, n){
if(a[i]>threshold)remove++;
}
cout<<remove;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“starter.txt”, “w”, stdout);
#endif
int t;
cin>>t;
// allPrimes();
// cout<<endl;
while(t–){
solve();
cout<<endl;
}
return 0;
}
where my code is failing please if someone know the testcase please share it with me.
my solution revolves arround the fact that a number that is of form 2^x-1 will have all ones in its binary except zero. so i am doing bitwise or off all the elements of the array then counting the coninuous ones from lsb, since that is the maximum ones we can get from all the numbers. then calculating the “int threshold = pow(2,count)-1” and now counting all the numbers that are grater than this threshold and printing that count. the following test explain my code.
testcase 1:
2 8 16 12
02=> 00010
08=> 01000
16=> 10000
12=> 01100
or=> 11110
^
the pointed bit can never be one no matter what number we remove from the elements.
Its bitwise or is = 30(11110), since all numbers are even then its lsb can never be one, hence we will have to remove all n numbers from the array.
testcase 2:
5
1 17 18 5 6
01=> 00001
17=> 10001
18=> 10010
05=> 00101
06=> 00110
or=> 10111
^
the pointed zero can never be one since at least one element of a should have 1 at that bit so all the numbers that are having 0 at that bit should be removed.
bitwise or = 23(10111)
conitnous ones = 3
so numbers greater than 7 can never make or equal to 2^x-1
i tried explain my solution but i am sorry if still there is some problem in my explantion. its because my english is poor.