CODEWITHSUNDEEP
algorithm
Shubh
Shubh

Reputation: 68

Find number of arrays with XOR sum equals to zero

How to determine number of arrays of length N such that it satisfies below two conditions:

  1. Each Value of array is between 0-5 inclusively.
  2. XOR sum of all value of the array is 0.

Example: Let N = 2

then total arrays with XOR sum zero = 6

which are- (0, 0) (1, 1) (2, 2) (3, 3) (4, 4) (5, 5)

So how to find out this in a efficient way?

Upvotes: 1

Views: 783

Answers (1)

fas
fas

Reputation: 1413

That could be done in O(N) using dynamic programming.

Let's say dp[i][j] is a number of arrays such that they have i elements and their XOR-sum is j.

Note that 0 <= j <= 7, because if N == 6 array [1, 2, 4, 4, 2, 1] matches, but it's prefix [1, 2, 4] has XOR-sum 7. Also you can't get XOR-sum more than 7 because all the numbers in range 0 to 5 can't have any other terms than 2^2, 2^1 and 2^0 when decomposed into powers of 2.

Here's the formula to calculate dp[i][j] using previously calculated values:

dp[i][j] = 0
# k is XOR-sum of previously calculated number of arrays of length i-1.
for k in range(0, 8):
    # x is a number we append to arrays of length i-1 so XOR-sum is j.
    x = j xor k
    if x <= 5:
        dp[i][j] += d[i - 1][k]

And that's the rest of code:

# Assume there's a two dimensional array of integers dp of size N+1 x 8.

# Dynamics initialization.
# There's only one possible array of length 0: []. It's XOR-sum is 0.
dp[0][0] = 1 
for i in range(1, 8):
    dp[0][i] = 0

# Dynamics state calculation.
for i in range(1, N+1):
    for j in range(0, 8):
        # Here comes code from above.
        dp[i][j] = 0
        for k in range(0, 8):
            x = j xor k
            if x <= 5:
                dp[i][j] += d[i - 1][k]

# Answer is dp[N][0].
print(dp[N][0])

Dynamics state calculation makes N*8*8 iterations, so complexity is O(N) (note that despite the linear complexity, the constant 64 might be quite large).

There is a way to make this be calculated in O(log N) using matrix binary exponentiation. Briefly: you need to calculate a 8x8 matrix M telling how dp[i-1][*] values turn to dp[i][*] values; then calculate dp[0] * M^N, where dp[0] is [1, 0, 0, 0, 0, 0, 0, 0] (exactly as in dynamics initialization).

Upvotes: 4

Related Questions