# Compute binary XOR of all integers in a range, mod 2

here I am taking 3 inputs. 1st input will take test cases and the other two input will take starting and ending range. the program is running fine as expected but the limit of this question for compilation is 1 sec, and my code is taking 5.01 sec.

How can I make it more efficient so that I can submit the code?

The challenge was to take number of test cases.

Each test cases show take 2 input (starting and ending range) Eg: 1 4 (i.e 1,2,3,4)

Do the bitwise XOR operation for all of them (i.e 1^2^3^4)

Which when you perform will be equal to 4

Now just check if it is even or odd and print the same.

Here's my code:

from sys import stdin, stdout
t = stdin.readline()
for i in range(int(t)):
p = 0
a, b = map(int,stdin.readline().split())
for x in range(a,b+1):
p ^= int(x)
if p % 2 == 0:
stdout.write(str("Even\n"))
else:
stdout.write(str("Odd\n"))


compiling in python 3.6

INPUT:
4
1 4
2 6
3 3
2 3

OUTPUT:
Even
Even
Odd
Odd


Working perfectly with no issue in code.

• Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Please check that I haven't misrepresented your code, and correct it if I have. Commented Jan 29, 2019 at 15:01

## 4 Answers

If you want to make this efficient you should avoid iterating over the range at all.

If you notice that the Xor of four consecutive integers is always even, you can "ignore" them in the final Xor and in the end you only care about the bounds modulo 4, and thus only have to read 4 bits of the input.

A one liner giving you the answer can be written as:

def answer(lo, hi):
return "Odd" if (((hi ^ lo) >> 1) ^ hi) & 1 else "Even"


Welcome to CR, nice challenge

A few comments about the code

• Many unnecessary conversion

Python is a duck typed language, if it talks like a duck, walks like a duck... it must be a duck!

This means that

p ^= int(x)


Here x is already an int, same goes for the str conversion later

• Use _ variable names for variable you don't use

for i in range(int(t)):

Replace the i with _

• You could return directly

if p % 2 == 0:
return "Even"
else:
return "Odd"


Instead, you could do which uses a ternary operator

return "Even" if p % 2 == 0 else "Odd"

• As for the speedup

I've used this SO link to inspire me, which does a way better job of explaining this then I could ever do

In short there is a trick to get the XOR'd product of a certain range

Using the method from the link, I get a massive speedup,

For these timings: range(1, 1000)

Bitmagic:  0.023904799999999997
OP: 2.2717274


# Code

# https://stackoverflow.com/questions/10670379/find-xor-of-all-numbers-in-a-given-range
def bit_magic(bound):
magic = [bound, 1, bound + 1, 0]
return magic[bound % 4]

def bitwise_check(lower_bound, upper_bound):
p = bit_magic(upper_bound) ^ bit_magic(lower_bound - 1)
return "Odd" if p & 1 else "Even"

def main():
n = int(input("Number of testcases: "))
for _ in range(n):
lower_bound, upper_bound = map(int, input().split())
print(bitwise_check(lower_bound, upper_bound))

if __name__ == '__main__':
main()

• For the return there is also the option return ["Even", "Odd"][p], but that might be too cryptic. Commented Jan 29, 2019 at 17:02
• Is there an objective reason to prefer the ternary to the if/else? I, personally, find the if/else construct more readable than the ternary (which hides the conditional in the middle of the results), and from what I can tell, both ways should result in the same bytecode.
– R.M.
Commented Jan 29, 2019 at 22:50
• @R.M. Agreed - I think if you want to shorten that, the more idiomatic way would be to leave off the else (given that it's redundant with a return in the if)
– sapi
Commented Jan 30, 2019 at 5:01
• @R.M. Not any objective reason, I find it to be more readable but YMMV Commented Jan 30, 2019 at 11:38
• @PeterTaylor normally I would advice against, but since the result can be only 1 or 0 not truthy or falsey, I think it's not super cryptic :) Commented Jan 30, 2019 at 11:43

If one has a range 1,2,3,4 then only every first bit is interesting for the result; in concreto: whether odd or even. If the number of odd numbers is odd, the result is odd.

def even (lwb, upb):
n = upb - lwb + 1;
ones = (n / 2) + (0 if n % 2 == 0 else (upb & 1))
return ones % 2 == 0


Here lwb (lower bound) and upb (upperbound) inclusive give a range of n numbers (odd even odd even ... or even odd even odd ...). ones is the number of odd.

This means that intelligent domain information can quite reduce the problem.

• When you use upb & 1, you may consistently replace all …% 2 with … & 1. This also allows to get rid of the conditional: ones = (n / 2) + (n & upb & 1). Commented Jan 30, 2019 at 13:39
• @Holger simplifies indeed. However I did not want to make the code too unreadable (needing an explanation). For instance def odd(lwb, upb) return 1&((n>>1)^(lwb&upb)). But indeed the odd/even test with modulo 2 is ugly looking. Commented Jan 30, 2019 at 14:21

The logic is straightforward and easy to follow (albeit with an unnecessary conversion of an int to an int):

p = 0
for x in range(a,b+1):
p ^= x
return p % 2


However, you could achieve the same more efficiently by noting that we're just counting how many odd numbers are in the range, and reporting whether that count is even or odd. That should suggest a simple O(1) algorithm in place of the O(n) algorithm you're currently using:

def count_odds(lo, hi):
'''
Count (modulo 2) how many odd numbers are in inclusive range lo..hi
>>> count_odds(0, 0)
0
>>> count_odds(0, 1)
1
>>> count_odds(1, 1)
1
>>> count_odds(0, 2)
1
>>> count_odds(1, 2)
1
>>> count_odds(2, 2)
0
>>> count_odds(0, 3)
2
>>> count_odds(1, 3)
2
>>> count_odds(2, 3)
1
>>> count_odds(3, 3)
1
'''
# if lo and hi are both odd, then we must round up,
# but if either is even, we must round down
return (hi + 1 - lo + (lo&1)) // 2

if __name__ == '__main__':
import doctest
doctest.testmod()


We can then use this function to index the appropriate string result:

if __name__ == '__main__':
for _ in range(int(input())):
a,b = map(int, input().split())
print(["Even","Odd"][count_odds(a,b) & 1])

• I lost you after "don't use p: just p % 2, which" Commented Jan 29, 2019 at 15:20
• @Akshansh, I've completely re-written that paragraph to make it clearer. Is that better? Commented Jan 29, 2019 at 16:25
• Since we're taking %2 or &1, only the low 2 bits of hi and lo matter; if we wanted to make sure this runs fast even with huge inputs (like 1 gigabyte long BigIntegers), we could narrow them before subtracting. But that would complicate the expression and slow down Python for the normal case. Commented Jan 30, 2019 at 10:13
• Yes @Peter, I thought of that and decided that clarity was more important for me. :-) Commented Jan 30, 2019 at 13:06