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

Question

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.

Answer 1

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"

Answer 2

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()

Answer 3

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.

Answer 4

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])