You are viewing a single comment's thread. Return to all comments →
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
if x == 1:
if x == 2:
for d in range(2, max(2, int(x**0.5)) + 1):
if x%d == 0:
return y//2 + 1
return y//2 + y%2
n = len(a)
c = Counter(a)
E = list(c.keys())
M = 8192
Sp =  * M
Sn =  * M
e = E
Sp[e] = get_nodds(c[e])
Sp = 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])
Sp = Sn
Sn =  * M
result = 0
for e in range(0, M):
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.