# TLE in ENGXOR

Continuing the discussion from ENGXOR - Editorial:

Why am I getting tle in subtask 2??
https://www.codechef.com/viewsolution/30429316

You are getting a TLE because your method for checking number of 1’s in query is O(n) you try using this method instead because it operates in O(1) time.

private static int meth(int a)
{
a^=a>>16;
a^=a>>8;
a^=a>>4;
a&=0xf;
return (0x6996 >> a) & 1;
}
It returns 1 for odd no of 1s and 0 for even

2 Likes

This property might come in hand(this is similar to XOR but kinda extended):

• XOR of two numbers where both have even/odd set bit count => Output has even set bits.

``````  Example:
x = 3   (011)  [HAS 2 SET BITS]
y = 15 (1111)  [HAS 4 SET BITS]

Both have even SET bits.
Their XOR is 12 (1100). It have even bits.
``````
• XOR of two numbers where both have different number of set bit(one has even bit and another has odd bits) => Output has odd set bits.

4 Likes

Yeah I have done the same
Checked for number of elements with even number of 1s(C1) and odd number of 1s(n-c1).
Then for each query if the query contains even number of 1s then print c1,n-c1 else n-c1,C1.

But Integer.bitCount uses O(1) time

The input/output is quite large, please use fast reading and writing methods.

yeah but i have used the fastest i/o method using datastream .

I don’t use Java so I can’t say.

1 Like

You didn’t. For fast output you need to use PrintWriter.

On line 142, I added: `PrintWriter out = new PrintWriter(System.out);`
On line 156&158 I replaced: `System.out.println` with `out.println`
On line 160, I added: `out.flush();`