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.

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.

## Prime XOR

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.

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.