Count Paths With the Given XOR Value

Medium
1672.

Count Paths With the Given XOR Value

Count Paths With the Given XOR Value is a medium coding problem on arrays, dynamic programming and matrix, asked in Google interviews.

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 <= 300
  • 1 <= n == grid[r].length <= 300
  • 0 <= grid[r][c] < 16
  • 0 <= k < 16
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var countPathsWithXorValue = function(grid, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 300
  • 1 <= n == grid[r].length <= 300
  • 0 <= grid[r][c] < 16
  • 0 <= k < 16

Hints for Count Paths With the Given XOR Value

  1. 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.

  2. Hint 2

    Add the running XOR to the state: dp[i][j][x] = number of paths from (0, 0) to (i, j) whose XOR is x.

  3. Hint 3

    A path reaching (i, j) with XOR x ^ grid[i][j] came from above or from the left with XOR x: 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

  1. Set dp[0][0][grid[0][0]] = 1.
  2. Visit cells row by row; for each cell (i, j) and each x in 0..15, set dp[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.
  3. 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