3393. Count Paths With the Given XOR Value LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3393. Count Paths With the Given XOR Value LeetCode Solution with the best time and space complexity. The solution to Count Paths With the Given XOR Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Paths With the Given XOR Value solution in C++
Count Paths With the Given XOR Value solution in Java
Count Paths With the Given XOR Value solution in Python
Additional Resources

3393. Count Paths With the Given XOR Value LeetCode Solution image

Problem Statement of Count Paths With the Given XOR Value

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. Formally, from the cell (i, j) you may move to the cell (i, j + 1) or to the cell (i + 1, j) if the target cell exists.
The XOR of all the numbers on the path must be equal to k.

Return the total number of such paths.
Since the answer can be very large, return the result modulo 109 + 7.

Example 1:

Input: grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]], k = 11
Output: 3
Explanation:
The 3 paths are:

(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2)
(0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2)
(0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2)

Example 2:

Input: grid = [[1, 3, 3, 3], [0, 3, 3, 2], [3, 0, 1, 1]], k = 2
Output: 5
Explanation:
The 5 paths are:

(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (2, 3)
(0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) → (2, 3)
(0, 0) → (1, 0) → (1, 1) → (1, 2) → (1, 3) → (2, 3)
(0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2) → (2, 3)
(0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (2, 3)

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

Complexity Analysis

Time Complexity: O(16mn) = O(mn)
Space Complexity: O(mn)

3393. Count Paths With the Given XOR Value LeetCode Solution in C++

class Solution {
 public:
  int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
    constexpr int kMax = 15;
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<vector<int>>> mem(
        m, vector<vector<int>>(n, vector<int>(kMax + 1, -1)));
    return count(grid, 0, 0, 0, k, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Return the number of paths from (i, j) to (m - 1, n - 1) with XOR value
  // `xors`.
  int count(const vector<vector<int>>& grid, int i, int j, int xors, int k,
            vector<vector<vector<int>>>& mem) {
    if (i == grid.size() || j == grid[0].size())
      return 0;
    xors ^= grid[i][j];
    if (i == grid.size() - 1 && j == grid[0].size() - 1)
      return xors == k ? 1 : 0;
    if (mem[i][j][xors] != -1)
      return mem[i][j][xors];
    const int right = count(grid, i, j + 1, xors, k, mem) % kMod;
    const int down = count(grid, i + 1, j, xors, k, mem) % kMod;
    return mem[i][j][xors] = (right + down) % kMod;
  }
};
/* code provided by PROGIEZ */

3393. Count Paths With the Given XOR Value LeetCode Solution in Java

class Solution {
  public int countPathsWithXorValue(int[][] grid, int k) {
    final int kMax = 15;
    final int m = grid.length;
    final int n = grid[0].length;
    Integer[][][] mem = new Integer[m][n][kMax + 1];
    return count(grid, 0, 0, 0, k, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Return the number of paths from (i, j) to (m - 1, n - 1) with XOR value
  // `xors`.
  private int count(int[][] grid, int i, int j, int xors, int k, Integer[][][] mem) {
    if (i == grid.length || j == grid[0].length)
      return 0;
    xors ^= grid[i][j];
    if (i == grid.length - 1 && j == grid[0].length - 1)
      return xors == k ? 1 : 0;
    if (mem[i][j][xors] != null)
      return mem[i][j][xors];
    final int right = count(grid, i, j + 1, xors, k, mem) % kMod;
    final int down = count(grid, i + 1, j, xors, k, mem) % kMod;
    return mem[i][j][xors] = (right + down) % kMod;
  }
}
// code provided by PROGIEZ

3393. Count Paths With the Given XOR Value LeetCode Solution in Python

class Solution:
  def countPathsWithXorValue(self, grid: list[list[int]], k: int) -> int:
    kMod = 1_000_000_007
    m = len(grid)
    n = len(grid[0])

    @functools.lru_cache(None)
    def count(i: int, j: int, xors: int) -> int:
      """
      Return the number of paths from (i, j) to (m - 1, n - 1) with XOR value
      `xors`.
      """
      if i == m or j == n:
        return 0
      xors ^= grid[i][j]
      if i == m - 1 and j == n - 1:
        return int(xors == k)
      right = count(i, j + 1, xors)
      down = count(i + 1, j, xors)
      return (right + down) % kMod

    return count(0, 0, 0)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents