LeetCode 3393 - Count Paths With the Given XOR Value

LeetCode Problem 3393

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Bit Manipulation, Matrix

Solution

Problem Understanding

The problem gives us an m x n grid where each cell contains a small integer value. We start at the top left corner (0, 0) and must reach the bottom right corner (m - 1, n - 1) by moving only right or down.

Along every path, we compute the XOR of all visited cell values. A path is considered valid if the final XOR equals k. Our task is to count how many such valid paths exist.

The result can become extremely large because the number of possible paths grows combinatorially. Because of that, we return the answer modulo 10^9 + 7.

The constraints are extremely important here:

• m, n <= 300
• Each cell value is between 0 and 15
• k < 16

The grid dimensions can be large, up to 300 x 300, which means there may be up to 90,000 cells. A brute force traversal of every possible path is impossible because the number of paths is exponential.

However, there is a very important observation: every grid value is less than 16. Since XOR only combines values bitwise, every possible XOR state is also in the range [0, 15].

That means there are only 16 possible XOR states at each cell.

This small XOR state space is the key to making dynamic programming feasible.

Some important edge cases include:

• A 1 x 1 grid where the answer depends entirely on whether grid[0][0] == k
• Cases where no path produces the required XOR
• Grids where multiple paths produce identical XOR states
• Large grids where efficiency and memory usage become critical
• Paths that revisit the same XOR value through different routes

The problem guarantees that all values are small enough for XOR state compression to work efficiently.

Approaches

Brute Force

The most direct approach is to enumerate every possible path from the top left to the bottom right.

At every cell, we have at most two choices:

• Move right
• Move down

For each complete path, we compute the XOR of all visited cells and check whether it equals k.

This approach is correct because it explicitly checks every valid path. However, it is far too slow.

A path from (0,0) to (m-1,n-1) contains exactly:

(m - 1) down moves
(n - 1) right moves

The number of unique paths is:

$\binom{m+n-2}{m-1}$

For a 300 x 300 grid, this number is astronomically large.

Therefore, brute force is not feasible.

Key Insight

The important observation is that XOR values are extremely limited.

Since every cell value is in [0, 15], the XOR of any collection of values also remains within [0, 15].

That means instead of tracking exponentially many paths, we only need to track:

(cell position, current XOR value)

This naturally leads to dynamic programming.

For each cell (i, j) and XOR value x, we store:

dp[i][j][x]

which represents:

Number of ways to reach cell (i, j)
with cumulative XOR equal to x

From each state, we transition:

• Down
• Right

while updating the XOR.

Because there are only 16 XOR states per cell, the total number of states is manageable.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(path length)	Enumerates every possible path
Optimal Dynamic Programming	O(m × n × 16)	O(m × n × 16)	Tracks only XOR states

Algorithm Walkthrough

1. Create a 3D DP table.

We define:

dp[i][j][x]

as the number of ways to reach cell (i, j) with XOR value x.

Since XOR values are only 0 through 15, the third dimension size is 16. 2. Initialize the starting position.

At the top left cell:

initial_xor = grid[0][0]

There is exactly one way to start there:

dp[0][0][grid[0][0]] = 1

3. Process every cell in row-major order.

For every cell (i, j) and every XOR state x:

• If dp[i][j][x] > 0, then this state is reachable.
• We propagate its count to neighboring cells.

4. Transition downward.

If (i + 1, j) exists:

• The new XOR becomes:

new_xor = x ^ grid[i + 1][j]

• Add the number of paths:

dp[i + 1][j][new_xor] += dp[i][j][x]

5. Transition rightward.

If (i, j + 1) exists:

• Compute the updated XOR:

new_xor = x ^ grid[i][j + 1]

• Add the count to the DP table.

6. Apply modulo arithmetic.

Every update is performed modulo:

MOD = 10^9 + 7

to avoid overflow. 7. Return the final answer.

The desired result is:

dp[m - 1][n - 1][k]

Why it works

The DP state fully captures everything needed to continue building valid paths:

• Current position
• Current XOR value

Any future decisions depend only on these two pieces of information.

Every valid path contributes exactly once to the appropriate DP state, and every transition correctly updates the XOR according to XOR properties. Therefore, by induction over the traversal order, the DP table contains the exact number of paths for every state.

Python Solution

from typing import List

class Solution:
    def countPathsWithXorValue(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        
        rows = len(grid)
        cols = len(grid[0])
        
        # dp[i][j][x] =
        # number of ways to reach (i, j)
        # with XOR value x
        dp = [[[0] * 16 for _ in range(cols)] for _ in range(rows)]
        
        start_xor = grid[0][0]
        dp[0][0][start_xor] = 1
        
        for i in range(rows):
            for j in range(cols):
                for xor_value in range(16):
                    current_paths = dp[i][j][xor_value]
                    
                    if current_paths == 0:
                        continue
                    
                    # Move down
                    if i + 1 < rows:
                        new_xor = xor_value ^ grid[i + 1][j]
                        dp[i + 1][j][new_xor] += current_paths
                        dp[i + 1][j][new_xor] %= MOD
                    
                    # Move right
                    if j + 1 < cols:
                        new_xor = xor_value ^ grid[i][j + 1]
                        dp[i][j + 1][new_xor] += current_paths
                        dp[i][j + 1][new_xor] %= MOD
        
        return dp[rows - 1][cols - 1][k]

The implementation directly mirrors the DP formulation.

We first allocate a 3D DP table with dimensions:

rows × cols × 16

The third dimension is fixed at 16 because XOR values never exceed 15.

The starting state initializes the XOR using the top left cell value.

We then iterate through every cell and every XOR state. If a state is reachable, we propagate its path count to neighboring cells while updating the XOR using the XOR operator.

Modulo arithmetic is applied during every update to keep numbers bounded.

Finally, we return the count stored at the bottom right cell with XOR equal to k.

Go Solution

package main

func countPathsWithXorValue(grid [][]int, k int) int {
	const MOD int = 1_000_000_007

	rows := len(grid)
	cols := len(grid[0])

	// dp[i][j][x]
	dp := make([][][]int, rows)

	for i := 0; i < rows; i++ {
		dp[i] = make([][]int, cols)

		for j := 0; j < cols; j++ {
			dp[i][j] = make([]int, 16)
		}
	}

	startXor := grid[0][0]
	dp[0][0][startXor] = 1

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			for xorValue := 0; xorValue < 16; xorValue++ {

				currentPaths := dp[i][j][xorValue]

				if currentPaths == 0 {
					continue
				}

				// Move down
				if i+1 < rows {
					newXor := xorValue ^ grid[i+1][j]

					dp[i+1][j][newXor] =
						(dp[i+1][j][newXor] + currentPaths) % MOD
				}

				// Move right
				if j+1 < cols {
					newXor := xorValue ^ grid[i][j+1]

					dp[i][j+1][newXor] =
						(dp[i][j+1][newXor] + currentPaths) % MOD
				}
			}
		}
	}

	return dp[rows-1][cols-1][k]
}

The Go implementation follows the same logic as the Python version.

One implementation detail is that Go requires explicit allocation of nested slices for the 3D DP table.

Another difference is modulo handling. Since Go integers can overflow in some environments, we apply modulo immediately after every update.

The XOR state dimension remains fixed at 16, keeping memory usage efficient.

Worked Examples

Example 1

Input:

grid =
[
  [2, 1, 5],
  [7,10, 0],
  [12,6, 4]
]

k = 11

Initial State

We begin at (0,0):

XOR = 2

So:

dp[0][0][2] = 1

Processing Cell (0,0)

Move	New Cell	XOR Calculation	New XOR
Down	(1,0)	2 ^ 7	5
Right	(0,1)	2 ^ 1	3

Now:

dp[1][0][5] = 1
dp[0][1][3] = 1

Processing Cell (1,0)

Current XOR state:

5

Transitions:

Move	New Cell	XOR Calculation	New XOR
Down	(2,0)	5 ^ 12	9
Right	(1,1)	5 ^ 10	15

Processing Cell (0,1)

Current XOR state:

3

Transitions:

Move	New Cell	XOR Calculation	New XOR
Down	(1,1)	3 ^ 10	9
Right	(0,2)	3 ^ 5	6

The algorithm continues similarly for all cells.

At the end:

dp[2][2][11] = 3

Therefore the answer is:

3

Example 2

Input:

grid =
[
  [1,3,3,3],
  [0,3,3,2],
  [3,0,1,1]
]

k = 2

Starting State

dp[0][0][1] = 1

First Expansion

Destination	XOR
(1,0)	1 ^ 0 = 1
(0,1)	1 ^ 3 = 2

Important Observation

Different paths can produce the same XOR state at the same cell.

For example, multiple routes may reach:

(i, j, xor = 2)

Instead of storing every path individually, the DP aggregates them into a count.

This compression is what makes the algorithm efficient.

After all transitions are processed:

dp[2][3][2] = 5

So the answer is:

5

Example 3

Input:

grid =
[
  [1,1,1,2],
  [3,0,3,2],
  [3,0,2,2]
]

k = 10

The DP explores all reachable XOR states.

However, no path ends with XOR 10.

Thus:

dp[2][3][10] = 0

The answer is:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n × 16)	Every cell processes 16 XOR states
Space	O(m × n × 16)	DP table stores all XOR states per cell

The XOR dimension is constant because values are constrained to [0,15].

Therefore, although the formal complexity includes 16, this is effectively linear in the number of cells.

For the maximum grid size:

300 × 300 × 16

the solution easily fits within time and memory limits.

Test Cases

from typing import List

class Solution:
    def countPathsWithXorValue(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        
        rows = len(grid)
        cols = len(grid[0])

        dp = [[[0] * 16 for _ in range(cols)] for _ in range(rows)]

        dp[0][0][grid[0][0]] = 1

        for i in range(rows):
            for j in range(cols):
                for x in range(16):

                    current = dp[i][j][x]

                    if current == 0:
                        continue

                    if i + 1 < rows:
                        nx = x ^ grid[i + 1][j]
                        dp[i + 1][j][nx] += current
                        dp[i + 1][j][nx] %= MOD

                    if j + 1 < cols:
                        nx = x ^ grid[i][j + 1]
                        dp[i][j + 1][nx] += current
                        dp[i][j + 1][nx] %= MOD

        return dp[-1][-1][k]

sol = Solution()

# Example 1
assert sol.countPathsWithXorValue(
    [[2,1,5],[7,10,0],[12,6,4]],
    11
) == 3  # basic example

# Example 2
assert sol.countPathsWithXorValue(
    [[1,3,3,3],[0,3,3,2],[3,0,1,1]],
    2
) == 5  # multiple valid paths

# Example 3
assert sol.countPathsWithXorValue(
    [[1,1,1,2],[3,0,3,2],[3,0,2,2]],
    10
) == 0  # no valid paths

# Single cell valid
assert sol.countPathsWithXorValue(
    [[5]],
    5
) == 1  # start equals target XOR

# Single cell invalid
assert sol.countPathsWithXorValue(
    [[5]],
    2
) == 0  # start does not match target XOR

# Two cells horizontal
assert sol.countPathsWithXorValue(
    [[1,2]],
    3
) == 1  # 1 ^ 2 = 3

# Two cells vertical
assert sol.countPathsWithXorValue(
    [[1],[2]],
    3
) == 1  # vertical movement only

# All zeros
assert sol.countPathsWithXorValue(
    [[0,0],[0,0]],
    0
) == 2  # both paths produce XOR 0

# XOR changes repeatedly
assert sol.countPathsWithXorValue(
    [[1,2],[3,4]],
    7
) == 1  # one valid XOR combination

# Larger repeated values
assert sol.countPathsWithXorValue(
    [[15]*5 for _ in range(5)],
    15
) >= 0  # stress repeated XOR states

Test Summary

Test	Why
Example 1	Verifies standard multi-path behavior
Example 2	Verifies aggregation of repeated XOR states
Example 3	Verifies zero valid paths
Single cell valid	Smallest possible valid grid
Single cell invalid	Smallest possible invalid grid
Two cells horizontal	Tests right-only movement
Two cells vertical	Tests down-only movement
All zeros	Tests repeated XOR identity behavior
XOR changes repeatedly	Tests correctness of XOR transitions
Large repeated grid	Stress test for DP scaling

Edge Cases

Single Cell Grid

A 1 x 1 grid is the smallest possible input. There are no moves, so the path consists only of the starting cell.

This case is easy to mishandle if the implementation assumes transitions are always required.

The solution handles it naturally because:

dp[0][0][grid[0][0]] = 1

and no transitions occur afterward.

No Valid Paths

Some grids may never produce the target XOR value.

A naive implementation might accidentally count partial matches or leave stale values in the DP table.

This implementation only updates states reachable through valid transitions, so unreachable XOR states remain 0.

Thus the final answer correctly becomes:

0

when no valid path exists.

Multiple Paths Sharing the Same XOR State

Different routes can reach the same cell with the same XOR.

If we tracked paths individually, the solution would become exponential.

The DP formulation correctly aggregates counts:

dp[i][j][xor]

stores the total number of such paths, regardless of how they were formed.

This compression is the central optimization that makes the algorithm efficient.

Large Grid Dimensions

With 300 x 300 cells, recursive DFS approaches risk stack overflow or exponential runtime.

The iterative DP approach avoids recursion entirely and processes each state exactly once, making it safe and efficient for the largest constraints.