# 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
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"? – 200_success Jan 26 '15 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? – 200_success Jan 26 '15 at 17:33
• my input constraint is 32 bit input ... so binary I meant 1 - '00000000000000000000000000000001' – lazarus Jan 26 '15 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? – 200_success Jan 26 '15 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. – 200_success Jan 26 '15 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 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. – Janne Karila Jan 27 '15 at 6:25
• Doesn't partial actually slow things down by wrapping the function call behind another function call, cf. Python functools partial efficiency? – Janne Karila Jan 27 '15 at 6:37