We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Prime XOR
  5. Discussions

Prime XOR

  • monkeycoder
     + 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.