# XOR of a list of a numbers

In preparing a solution for the CodeChef "Will India Win" challenge, I am trying to find out the xor of list of numbers.

The first line of input contains the number of test cases, 1 ≤ T ≤ 106.
Subsequent lines contain fifteen space-delimited numbers (each between 1 and 231), to be XORed together.

def main():
t = int(raw_input())
for i in range(t):

input_list = [int(j) for j in raw_input().split()]
res = input_list[0]
for n in range(len(input_list)-1):
res = res^input_list[n+1]
print res

if __name__ == '__main__':
main()


Here is my second code by implementing a 2D array through a dictionary:

def main():
t = int(raw_input())
for i in range(t):
input_str = [ int(j) for j in raw_input().split()]
d = {}
for j in range(15):
d[j] = bin(input_str[j])[2:].zfill(32)

l = []#contains the final output
for j in range(32):
temp = 0
for k in range(15):
if d[k][j] == '1':
temp += 1

if temp%2 == 0:
l.append(0)
else:
l.append(1)
if  __name__ == '__main__':
name()


But it turns out that both code are not optimal because I am getting time constraint problems. How can I optimize the code?

• What do you mean by "in binary format"? Commented Jan 26, 2015 at 17:32
• Could you say more about the time constraints? How long is your input list, what is the desired running time, and how long do these solutions take? Commented Jan 26, 2015 at 17:33
• my input constraint is 32 bit input ... so binary I meant 1 - '00000000000000000000000000000001' Commented Jan 26, 2015 at 17:36
• I still don't understand. Could you edit the question to include a concrete example of what the input and output should look like? Commented Jan 26, 2015 at 17:38
• It's a horribly written challenge. "In binary format" is contradicted by the example input, which shows decimal numbers. Jercy [sic] numbers up to 2^31 are also not realistic. Commented Jan 26, 2015 at 23:42

As the input size is 10**6 and you're using Python 2 the first issue in that you're creating an unnecessary list of 10**6 integers just to do a loop.

Instead of that you should use xrange() which yields integers lazily:

>>> %timeit for _ in range(10**6): pass
10 loops, best of 3: 24.1 ms per loop
>>> %timeit for _ in xrange(10**6): pass
f100 loops, best of 3: 8.92 ms per loop


Another slight micro-optimization that you can do here is to use itertools.repeat with None. None is a singleton, so, only a single None ever exists in memory and it is the smallest object in CPython on the other hand creating 10**6 integers is expensive(well CPython caches some of them, but still they are unnecessary here)

>>> %timeit for _ in repeat(None, 10**6): pass
100 loops, best of 3: 7 ms per loop


As we're using the functions like raw_input, int multiple times in our code it's better to cache them as local variables, because otherwise we're looking for them at least 10**6 times in global dictionary. One way to cache them is to use them as default values to function attributes:

>>> def f_simple(n):
for _ in xrange(n):
foo = [int('1') for _ in xrange(15)]
...
>>> def f_cached(n, int=int):
for _ in xrange(n):
foo = [int('1') for _ in xrange(15)]
...
>>> %timeit f_simple(10**6)
1 loops, best of 3: 3.7 s per loop
>>> %timeit f_cached(10**6)
1 loops, best of 3: 3.52 s per loop


Instead of starting the result value with input_list[0] we can simply start with 0 and we can also prevent creation of that simple 15 items list:

result = 0
for x in raw_input().split():
result ^= int(x)


Currently your first solution takes around 7.44 seconds on my system and my solution takes around 5.6 seconds, not a huge improvement.:

from itertools import islice
from functools import partial
import sys

def main5(int=int):
t = int(raw_input())
# Take a slice of sys.stdin of size (10**6)*2
lines = islice(sys.stdin, t*2)
# Now lines is an iterator which is going to yield one
# line at a time, but we're also going to read the next line(to get X)
# with each input, so instead of doing next(lines) each time in
# the loop we can create a partial function.
next_line = partial(next, lines)

for line in lines:
result = 0
for x in line.split():
result ^= int(x)
if format(result, 'b').zfill(32).count('1') > int(next_line()):
print 'YES'
else:
print 'NO'


Note that in the above solution we are writing to the stdout instantly, if we can store the output temporarily in a list(say 1000 items) and them write them at once then the above solution takes 5.52 seconds:

from itertools import islice
from functools import partial
import sys

def main6(int=int, len=len):
t = int(raw_input())
# store a reference sys.stdout.write to prevent 2 attribute lookups
stdout_write = sys.stdout.write
lines = islice(sys.stdin, t*2)
next_line = partial(next, lines)
out = []
# Cache out.append to prevent attribute lookup
out_append = out.append
for line in lines:
result = 0
for x in line.split():
result ^= int(x)
if format(result, 'b').zfill(32).count('1') > int(next_line()):
result = 'YES'
else:
result = 'NO'

out_append(result)
if len(out) == 1000:
stdout_write('\n'.join(out))
# empty out list; use list.clear() in Python 3
del out[:]
if out:
stdout_write('\n'.join(out))

• You can skip the zfill because only 1's count. Commented Jan 27, 2015 at 6:25
• Doesn't partial actually slow things down by wrapping the function call behind another function call, cf. Python functools partial efficiency? Commented Jan 27, 2015 at 6:37