Https://www.codechef.com/viewsolution/1071166614

general
1

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.

2

@savetreelife
here plzz refer the following c++ code

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    long long int n;
	    cin>>n;
	    long long int a[n];
	    long long int sm=0,p=1;
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	        sm=sm|a[i];
	    }
	    while(p<=sm)
	    {
	        long long ch=p&sm;
	        if(ch!=p)
	        {
	            break;
	        }
	        else
	        p=p*2;
	    }
	    int ans=0;
	    for(int i=0;i<n;i++)
	    {
	        if(a[i]>=p)
	        ans++;
	    }
	    cout<<ans<<endl;
	}
	return 0;
}
3

Thanks for the solution. Please help me find why my code is not valid solution. It will really be helpfull.

4

@savetreelife
bro your solution is absolutely fine .
May be its getting integer overflow issue and u have declared macro file for int to long long so that wouldn’t be the issue ,try to ignore left right shift operation and do it in simpler looping way to calculate the 2’s power …i’m not sure that would help or not but atleast u can try.

5

I also solved the problem by the same logic and all test cases passed. You can view the solution on my profile. May be your code is not running because you have declared all variables of int datatype instead of long long.

But the point is testcases are not sufficient for this problem. This logic is failing at a test case.
Example:
137=> 10001001
22 => 10110
or=> 10011111
so we have to remove numbers greater than 31 as there are continuous 5 1’s.
after removing 137 , we are left with 22 which is 10110 and it is not of the form 2^x-1.

6

hi thanks a lot for your help guys, i really appreciate.
From my code i just removed this if((ored&1ll)==0){cout<<n;return;} line and my solution worked fine.
now as i think the or of all the numbers will be even only if every number of array is even no other way is possible. then why my code fails?