# Prime XOR

# Prime XOR

+ 2 comments It seems to me that if there exists a solution, then there exists infinitely many solutions. For, given a solution S, simply add two occurances of any element to S. For instance, S + {3501, 3501} will also be a solution, and by the definition of multisets is a distinct multiset from S.

+ 4 comments Finally got AC by DP, some of my thoughts here:

Note the uppper bound of N is 1e5, it tells us to come up with a linear or NlogN solution for each case, but I failed.

So let's look at the range of a[i], it's in [3500, 4500], much smaller than range of N, furthermore, the XOR of any multiset must be in range [0, 8191] (8191==2^13-1). These two observations are the key to my DP solution:

Count the number of each unique integer in input array, then for each unique number, I enumerate every possible integer in [0, 8191] and do some simple calculation to get the number of multiset.

The time complexity of my DP solution is O(M*P), M is the number of unique input integers, P is the range of possible XOR sum, so the upper bound of N*M is 1e7, quite resonable.

+ 1 comment A simple solution in Python is below. It unfortunately times out in larger test cases despite runtime complexity being the same as other solutions.

Note that the solution below uses less space than other solutions that store a full two dimensional array for dynamic programming.

from collections import Counter import sys def isPrime(x): if x == 1: return False if x == 2: return True for d in range(2, max(2, int(x**0.5)) + 1): if x%d == 0: return False return True def get_nevens(y): return y//2 + 1 def get_nodds(y): return y//2 + y%2 def primeXor(a): n = len(a) c = Counter(a) E = list(c.keys()) M = 8192 Sp = [0] * M Sn = [0] * M e = E[0] Sp[e] = get_nodds(c[e]) Sp[0] = get_nevens(c[e]) for e in E[1:]: for x in range(0, M): Sn[x^e] += Sp[x] * get_nodds(c[e]) Sn[x] += Sp[x] * get_nevens(c[e]) # next Sp = Sn Sn = [0] * M result = 0 for e in range(0, M): if isPrime(e): result += Sp[e] return int(result%(1e9 + 7))

The key to understand the dynamic programming solution is that the solution needs not propagate the "primeness". In other words, dynamic programming in this case is not aware of anything being prime. It merely propagates all possible XOR sums (i.e. 0 to 8192 - 1) and later tallies up which XOR sums are primes. A more technical way of saying is that optimal substructure does not involve primeness but rather simple XOR sums.

+ 0 comments For everyone having trouble passing the last few testcases in python, just copy your code into pypy and it should speed it up enough to get you through the last few :)

+ 1 comment I have implemented the same solution in Java and Python 2, and the Python solution times out on some larger cases while the Java solution works. My solution is the same as the editorial. It also seems like no one has submitted a Python solution which gets full score, so it seems like the constraints make it impossible to solve in Python.

Sort 38 Discussions, By:

Please Login in order to post a comment