Shivkumar - 1 year ago 120

Python Question

I have solved this problem from hackerearth.com using python(v2)

Problem statement: Xor is Mad

My code is :

`tests = int(raw_input())`

for i in range(tests):

x = int(raw_input())

c = 0

b = x

a = x-1

while a > 0:

xor = a^b

summ = b + a

# print "XOr : ",xor

# print "Sum : ",summ,"\n--------"

if xor == summ:

c += 1

a -= 1

elif a > 0:

a -= 1

print c

but I have time exceeding problem for inputs : input#5 to #9

can somebody solve this problem in different way to manage the tests to be executed in 1sec.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

The trick is to recognize that you don't have to test all the `a`

up to `x`

. For `a^x == a+x`

, then `a&x == 0`

. So we count the number of zeroes in the bitstring of `x`

and then out answer is `2**count -1`

```
test = int(input())
for _ in range(test):
x = int(input())
print(2**bin(x)[2:].count('0') -1)
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**