Count paths with the given xor value

Array Dynamic Programming Bit Manipulation Matrix

40.5% acceptance

Feb 24, 2026

You are given a 2D integer array grid with size m x n. You are also given an integer k. Your task is to calculate the number of paths you can take from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) satisfying the following constraints: You can either move to the right or down. The XOR of all the numbers on the path must be equal to k. Return the total number of such paths modulo 10^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_paths_with_xor_value(grid: Vec<Vec<i32>>, k: i32) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let md = 1_000_000_007i64;
    
    // dp[i][j][x] = number of paths to (i,j) with XOR value x
    // XOR values are 0..15 (grid values < 16)
    let mut dp = vec![vec![vec![0i64; 16]; n]; m];
    dp[0][0][grid[0][0] as usize] = 1;
    
    for i in 0..m {
      for j in 0..n {
        if i == 0 && j == 0 { continue; }
        let g = grid[i][j] as usize;
        for x in 0..16 {
          let mut cnt = 0i64;
          if i > 0 { cnt += dp[i-1][j][x]; }
          if j > 0 { cnt += dp[i][j-1][x]; }
          dp[i][j][x ^ g] = (dp[i][j][x ^ g] + cnt) % md;
        }
      }
    }
    
    dp[m-1][n-1][k as usize] as i32
  }
}