import sys
from sys import stdin, stdout
T=int(stdin.readline())
for x in range(0,T):
N,Q = map(int,input().split())
A = list(map(int,input().split()))
for q in range (0,Q):
P=int(stdin.readline())
x = bin§.count(‘1’)
eve = 0
for i in range(0,N):
y = bin(A[i]).count(‘1’)
if x%2 ==0:
if y%2 ==0:
eve = eve+1
else:
if y%2!=0:
eve = eve+1
"Tnstead of __builtin_popcount(x) we can directly use __builtin_parity(x)
basically if f(N) represents nu[quote=“kabirsingh2027, post:9, topic:56715, full:true”]
Instead of __builtin_popcount(x) we can directly use __builtin_parity(x)
basically if f(N) represents number of set bits in binary representation of N, then
f(N xor K) = f(N) xor f(K)
where f(x) is __builtin_parity(x), a built-in function in C++.
[/quote]
mber of set bits in binary representation of N, then
f(N xor K) = f(N) xor f(K)
where f(x) is __builtin_parity(x), a built-in function in C++."
This is wrong . say f is popcount then f(1 xor 1) = 0 != 1 + 1 =2 . Are you sure ? It doesnt even work for parity,
@tmwilliamlin Hey can you please tell why i am getting tle by making seperate funtion for counting set bits insted of __buitin_parity(x)
here is the code getting tle
#include<bits/stdc++.h>
using namespace std;
int count_bits(int k)
{
int b;
while(k)
{
b+=k%2;
k/=2;
}
return b%2;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int a,i,n,q,cr[2]={};
cin>>n>>q;
for(i=0;i<n;++i)
{
cin>>a;
++cr[count_bits(a)];
}
for(int p; q--; ) {
cin >> p;
int z=count_bits(p);
cout << cr[z] << " " << cr[z^1] << "\n";
}
}
}
while if i replace the count_bits function by __buitin_parity the soln gets accepted.
Please help.
Thanks in advance.
brother when you are calling a function it take time suppose your (t ,n) is large and so it is O(nq) time which is large to constrain so thats why its going to tle.
Hi,
Can anyone suggest me how do I get rid of TLE in subtask 2
(PYTH 3.6) https://www.codechef.com/viewsolution/30579279
Not very sure how to improve my program(This is my first time working with bits).
Thankyou
int countOne(int n)
{
int count = 0;
while (n)
{
n = n & (n - 1);
count++;
}
if (count % 2 == 0)
return 1;
else
return 0;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t–)
{
int n, q;
cin >> n >> q;
int arr[n];
for (int i = 0; i < n; ++i)
cin >> arr[i];
while (q--)
{
int p;
cin >> p;
int even = 0;
for (int i = 0; i < n; ++i)
{
arr[i] ^= p;
if (countOne(arr[i]))
even++;
}
cout << even << " " << n - even << endl;
}
}
return 0;
Because for every Test Case, Your array will get updated and in question the array to be used is the original one only.
You have to Xor new P’s with the old array for the given test cases in queries.
You need to keep a utility array for new operations
why this code is giving compilation error, prog.cpp:5:10: error: ‘::main’ must return ‘int’
int main()
#include<bits/stdc++.h> #define int long long int #define endl “\n”
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n,p;
cin>>n>>p;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int even=0,odd=0;
for(int i=0;i<n;i++)
{
int check = __builtin_popcount(a[i]);
if(check%2==0)
even++;
else
odd++;
}
while(p--)
{
int input;
cin>>input;
int even1=even,odd1=odd;
int check1 = __builtin_popcount(input);
if(check1%2!=0)
{
even1=odd;
odd1=even;
}
cout<<even1<<" "<<odd1<<endl;
}
}
return 0;
public static void main (String[]args) throws java.lang.Exception
{
// your code goes here
Reader in = new Reader();
int t = in.nextInt ();
for (int i = 0; i < t; i++)
{
int n = in.nextInt();
int q = in.nextInt();
int odd=0;
int even=0;
for (int j = 0; j<n ; j++)
{
if (Integer.bitCount(in.nextInt())%2==0) even++;
else odd++;
}
for (int j = 0; j<q;j++)
{
int p =in.nextInt();
if (Integer.bitCount(p)%2==0)
{
System.out.println(even + " " + odd);
}
else System.out.println(odd + " " + even);
}
}