3659. Count Paths With The Given Xor Value¶

3659. Count Paths With the Given XOR Value

Medium

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 10⁹ + 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

Solution¶

class Solution {
    private int mod = (int)(1e9 + 7);
    private int dp[][][];
    public int countPathsWithXorValue(int[][] grid, int k) {
        int n = grid.length, m = grid[0].length;
        dp = new int[n + 1][m + 1][20];
        for (int current[][] : dp) for (int current1[] : current) Arrays.fill(current1, -1);
        int res = solve(0, 0, 0, grid, k);
        return res;
    }
    private int solve(int row, int col, int xor, int grid[][], int k) {
        if (row >= grid.length || col >= grid[0].length) return 0;
        xor ^= grid[row][col];
        if (row == grid.length - 1 && col == grid[0].length - 1) return xor == k ? 1 : 0;
        if (dp[row][col][xor] != -1) return dp[row][col][xor];
        int op1 = solve(row + 1, col, xor, grid, k);
        int op2 = solve(row, col + 1, xor, grid, k);
        return dp[row][col][xor] = (op1 + op2) % mod;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]