Count Paths With the Given XOR Value — Problem & Solution
Count Paths With the Given XOR Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Paths With the Given XOR Value is a medium coding problem on arrays, dynamic programming and matrix, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix, Bit Manipulation
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n integer matrix grid and an integer k.
Count the paths from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) that move only right or down at each step, such that the XOR of all the values on the path (both ends included) equals k.
Return the count modulo 10^9 + 7.
Example 1
Input: grid = [[2,1,5],[7,10,0],[12,6,4]], k = 11
Output: 3
Explanation: 2→7→12→6→4, 2→7→10→0→4 and 2→1→10→6→4 all XOR to 11.
Example 2
Input: grid = [[1,3,3,3],[0,3,3,2],[3,0,1,1]], k = 2
Output: 5
Example 3
Input: grid = [[1,1,1,2],[3,0,3,2],[3,0,2,2]], k = 10
Output: 0
Constraints
1 <= m == grid.length <= 3001 <= n == grid[r].length <= 3000 <= grid[r][c] < 160 <= k < 16
Hints for Count Paths With the Given XOR Value
Hint 1
Counting all paths with a fixed sum would be hard, but here every value is below 16 — so every XOR along a path is below 16 too.
Hint 2
Add the running XOR to the state:
dp[i][j][x]= number of paths from(0, 0)to(i, j)whose XOR isx.Hint 3
A path reaching
(i, j)with XORx ^ grid[i][j]came from above or from the left with XORx:dp[i][j][x ^ grid[i][j]] = dp[i - 1][j][x] + dp[i][j - 1][x].
How to solve Count Paths With the Given XOR Value
The usual grid-path DP counts paths per cell; here the count must be split by the XOR so far. Because all values are below 16, there are only 16 possible XORs, so each cell holds 16 counters.
Approach
- Set
dp[0][0][grid[0][0]] = 1. - Visit cells row by row; for each cell
(i, j)and eachxin0..15, setdp[i][j][x ^ grid[i][j]] = (dp[i - 1][j][x] + dp[i][j - 1][x]) mod 10^9 + 7, treating missing neighbours as 0. - Return
dp[m - 1][n - 1][k].
Why it works
Every path to (i, j) other than the start enters from exactly one of the two neighbours, and its XOR is the neighbour path's XOR combined with grid[i][j]. Since x -> x ^ v is a bijection on 0..15, each neighbour state feeds exactly one state of the cell, so the counts add without double counting.
Complexity
- Time —
O(m · n · 16) - Space —
O(m · n · 16)
Pitfalls
- Include both the start and the end cell values in the XOR.
- Reduce modulo
10^9 + 7— path counts in a 300 × 300 grid are astronomically large.
Reference solution
Python
from typing import List
def countPathsWithXorValue(grid: List[List[int]], k: int) -> int:
MOD = 10**9 + 7
m, n = len(grid), len(grid[0])
dp = [[[0] * 16 for _ in range(n)] for _ in range(m)]
dp[0][0][grid[0][0]] = 1
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
v = grid[i][j]
up = dp[i - 1][j] if i > 0 else None
left = dp[i][j - 1] if j > 0 else None
cur = dp[i][j]
for x in range(16):
c = 0
if up is not None:
c += up[x]
if left is not None:
c += left[x]
cur[x ^ v] = c % MOD
return dp[m - 1][n - 1][k]Java
public static int countPathsWithXorValue(int[][] grid, int k) {
final int MOD = 1000000007;
int m = grid.length, n = grid[0].length;
int[][][] dp = new int[m][n][16];
dp[0][0][grid[0][0]] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
int v = grid[i][j];
for (int x = 0; x < 16; x++) {
long c = 0;
if (i > 0) c += dp[i - 1][j][x];
if (j > 0) c += dp[i][j - 1][x];
dp[i][j][x ^ v] = (int) (c % MOD);
}
}
}
return dp[m - 1][n - 1][k];
}C++
int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
const int MOD = 1000000007;
int m = grid.size(), n = grid[0].size();
vector<vector<array<int, 16>>> dp(m, vector<array<int, 16>>(n));
for (auto& row : dp) for (auto& cell : row) cell.fill(0);
dp[0][0][grid[0][0]] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
int v = grid[i][j];
for (int x = 0; x < 16; x++) {
long long c = 0;
if (i > 0) c += dp[i - 1][j][x];
if (j > 0) c += dp[i][j - 1][x];
dp[i][j][x ^ v] = (int) (c % MOD);
}
}
}
return dp[m - 1][n - 1][k];
}JavaScript
var countPathsWithXorValue = function(grid, k) {
var MOD = 1000000007;
var m = grid.length, n = grid[0].length;
var dp = [];
for (var i = 0; i < m; i++) {
var row = [];
for (var j = 0; j < n; j++) row.push(new Array(16).fill(0));
dp.push(row);
}
dp[0][0][grid[0][0]] = 1;
for (var r = 0; r < m; r++) {
for (var c = 0; c < n; c++) {
if (r === 0 && c === 0) continue;
var v = grid[r][c];
for (var x = 0; x < 16; x++) {
var cnt = 0;
if (r > 0) cnt += dp[r - 1][c][x];
if (c > 0) cnt += dp[r][c - 1][x];
dp[r][c][x ^ v] = cnt % MOD;
}
}
}
return dp[m - 1][n - 1][k];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming