Count Paths With the Given XOR Value
MedPrompt
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
XORof all the numbers on the path must be equal tok.
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 <= 3001 <= n == grid[r].length <= 3000 <= grid[r][c] < 160 <= k < 16
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible path from the starting cell (0, 0) to the destination (m-1, n-1). For each path, it calculates the XOR sum of the values of the cells along the path. If the final XOR sum equals k, it counts that path. This is implemented using a recursive function that explores moving right and down from the current cell.
Algorithm
- Define a recursive function
solve(row, col, currentXor). - The function represents the number of valid paths from
(row, col)to the destination, given the XOR sum of the path from(0,0)to the cell before(row, col)iscurrentXor. - Base Case 1: If
roworcolis out of grid bounds, it's an invalid path. Return 0. - Base Case 2: If
(row, col)is the destination(m-1, n-1), calculate the final XOR sumfinalXor = currentXor ^ grid[row][col]. IffinalXor == k, return 1, otherwise return 0. - Recursive Step: Update the XOR sum:
newXor = currentXor ^ grid[row][col]. Recursively call for moving down and right:solve(row + 1, col, newXor)andsolve(row, col + 1, newXor). Return the sum of their results. - The initial call is
solve(0, 0, 0).
Walkthrough
We define a recursive function, say solve(row, col, currentXor). This function calculates the number of valid paths starting from (row, col) given that the XOR sum of the path from (0,0) up to the cell before (row, col) is currentXor. The base case for the recursion is when we reach the destination cell (m-1, n-1). At this point, we calculate the final XOR sum by XORing currentXor with grid[m-1][n-1]. If this equals k, we have found a valid path and return 1. Otherwise, we return 0. Another base case is if the current cell (row, col) is out of the grid boundaries, in which case we return 0. In the recursive step, from cell (row, col), we update the XOR sum and make two recursive calls: one for moving down solve(row + 1, col, newXor) and one for moving right solve(row, col + 1, newXor). The total number of paths is the sum of the results from these two calls. The initial call would be solve(0, 0, 0).
class Solution { int m, n, k; int[][] grid; int MOD = 1_000_000_007; public int numberOfPaths(int[][] grid, int k) { this.m = grid.length; this.n = grid[0].length; this.k = k; this.grid = grid; // Note: This will time out. A memoization table is needed. return solve(0, 0, 0); } private int solve(int r, int c, int currentXor) { if (r >= m || c >= n) { return 0; } int newXor = currentXor ^ grid[r][c]; if (r == m - 1 && c == n - 1) { return (newXor == k) ? 1 : 0; } int pathsDown = solve(r + 1, c, newXor); int pathsRight = solve(r, c + 1, newXor); return (pathsDown + pathsRight) % MOD; }}Complexity
Time
O(2^(m+n)). The number of paths from `(0,0)` to `(m-1, n-1)` is given by the binomial coefficient `C(m+n-2, m-1)`, which grows exponentially.
Space
O(m + n), for the recursion stack depth, which is the length of a path.
Trade-offs
Pros
Simple to understand and implement.
It correctly models the problem's logic.
Cons
Extremely inefficient due to exponential time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Recalculates solutions for the same subproblems (same cell and same XOR sum) repeatedly.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.