# Count Paths With the Given XOR Value **Difficulty:** MEDIUM [External](https://leetcode.com/problems/count-paths-with-the-given-xor-value) Canonical: https://scaleengineer.com/dsa/problems/count-paths-with-the-given-xor-value **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation) **Data structures:** Array, Matrix --- ## Problem 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` # Approaches ## Brute-Force Recursion 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. **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. **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. ### Explanation 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)`. ```java 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; } } ``` ### 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)` is `currentXor`. - **Base Case 1**: If `row` or `col` is 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 sum `finalXor = currentXor ^ grid[row][col]`. If `finalXor == 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)` and `solve(row, col + 1, newXor)`. Return the sum of their results. - The initial call is `solve(0, 0, 0)`. ## Bottom-Up Dynamic Programming This approach improves upon the brute-force method by using dynamic programming to avoid recomputing results for the same subproblems. A subproblem can be uniquely identified by the current cell `(r, c)` and the current path's XOR sum. We use a 3D array `dp[r][c][xor_val]` to store the number of paths from `(0, 0)` to `(r, c)` with a path XOR sum of `xor_val`. A key observation is that since all grid values are less than 16, any XOR sum of these values will also be less than 16. This keeps the third dimension of our DP table small and manageable. **Time:** O(m * n * C), where `C` is the maximum possible XOR value (16). We iterate through each cell, and for each cell, we iterate through all possible XOR values. · **Space:** O(m * n * C), where `C` is the maximum possible XOR value (16). This is for the 3D DP table. **Pros:** Efficient and guaranteed to find the correct solution within time limits.; Avoids recursion overhead compared to a top-down memoized approach.; The logic is a standard grid DP pattern. **Cons:** Uses a significant amount of memory, `O(m * n * C)`, which might be an issue for very large grids, although it's acceptable for the given constraints. ### Explanation We define a 3D DP table `dp[m][n][16]`, where `dp[i][j][x]` stores the number of paths from the start `(0, 0)` to cell `(i, j)` such that the XOR sum of elements along the path is `x`. This can be implemented using a bottom-up (tabulation) approach for efficiency. We initialize `dp[0][0][grid[0][0]] = 1` as there is one way to be at the starting cell with an XOR sum equal to its own value. Then, we iterate through the grid. For any cell `(i, j)`, the paths to it can only come from the cell above, `(i-1, j)`, or the cell to the left, `(i, j-1)`. For each possible XOR sum `x` at cell `(i, j)`, we find the required XOR sum at the previous cells. If we are at `(i, j)` with XOR sum `x`, we must have been at `(i-1, j)` or `(i, j-1)` with an XOR sum of `x ^ grid[i][j]`. So, we sum up the counts from these previous states: `dp[i][j][x] = (dp[i-1][j][x ^ grid[i][j]] + dp[i][j-1][x ^ grid[i][j]])`. We perform this for all possible XOR values from 0 to 15. The final answer is the number of paths to the destination cell `(m-1, n-1)` with an XOR sum of `k`, which is `dp[m-1][n-1][k]`. ```java class Solution { public int numberOfPaths(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; int MOD = 1_000_000_007; int MAX_XOR_VAL = 16; long[][][] dp = new long[m][n][MAX_XOR_VAL]; // Base case: starting cell 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 currentVal = grid[i][j]; for (int x = 0; x < MAX_XOR_VAL; x++) { int prevXor = x ^ currentVal; long pathsFromUp = (i > 0) ? dp[i - 1][j][prevXor] : 0; long pathsFromLeft = (j > 0) ? dp[i][j - 1][prevXor] : 0; dp[i][j][x] = (pathsFromUp + pathsFromLeft) % MOD; } } } return (int) dp[m - 1][n - 1][k]; } } ``` ### Algorithm - Create a 3D DP table `dp[m][n][C]`, where `C` is the maximum possible XOR value (16). - `dp[i][j][x]` will store the number of paths from `(0,0)` to `(i,j)` with a path XOR sum of `x`. - **Initialization**: Set `dp[0][0][grid[0][0]] = 1`. All other entries are 0. - **Transition**: Iterate through each cell `(i, j)` from top-left to bottom-right. For each cell, calculate the number of paths reaching it. - The number of paths to `(i, j)` with XOR sum `x` is the sum of paths from `(i-1, j)` and `(i, j-1)` that result in this XOR sum. - The recurrence relation is: `dp[i][j][x] = (dp[i-1][j][x ^ grid[i][j]] + dp[i][j-1][x ^ grid[i][j]]) % MOD`. - We iterate `i` from 0 to `m-1`, `j` from 0 to `n-1`, and for each cell, we iterate through all possible XOR values `x` from 0 to `C-1` to apply the recurrence. - **Result**: The final answer is `dp[m-1][n-1][k]`. ## Space-Optimized Dynamic Programming This approach optimizes the space complexity of the standard DP solution. We observe that to compute the DP values for the current row `i`, we only need the DP values from the previous row `i-1`. This dependency allows us to reduce the DP table's dimension from `m x n x C` to `n x C`, using space proportional to the number of columns instead of the whole grid. **Time:** O(m * n * C), same as the standard DP approach. · **Space:** O(n * C), where `n` is the number of columns and `C` is 16. If `m < n`, we can optimize further to `O(m * C)` by iterating column by column. **Pros:** Most memory-efficient solution.; Retains the optimal time complexity of the standard DP approach. **Cons:** The logic for in-place updates can be slightly more complex to reason about and implement correctly compared to the standard DP approach. ### Explanation The space optimization is based on the observation that the DP calculation for a cell `(i, j)` only depends on `(i-1, j)` and `(i, j-1)`. This means when computing values for row `i`, we only need the results from row `i-1`. We can discard the results from rows `i-2` and earlier. We can use a 2D array `dp[n][C]` to store the path counts for the current row being processed. As we iterate from row `i` to `i+1`, the `dp` array is updated to reflect the counts for the new row. Let `dp[j][x]` be the number of paths to `(i, j)` with XOR sum `x`. When we compute for row `i`, we update the `dp` array. The new value for `dp[j]` will depend on its old value (which corresponds to `(i-1, j)`) and the just-computed value of `dp[j-1]` (which corresponds to `(i, j-1)`). ```java class Solution { public int numberOfPaths(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; int MOD = 1_000_000_007; int MAX_XOR_VAL = 16; long[][] dp = new long[n][MAX_XOR_VAL]; // Initialize for row 0 dp[0][grid[0][0]] = 1; for (int j = 1; j < n; j++) { int currentVal = grid[0][j]; for (int x = 0; x < MAX_XOR_VAL; x++) { if (dp[j - 1][x] > 0) { dp[j][x ^ currentVal] = (dp[j][x ^ currentVal] + dp[j - 1][x]) % MOD; } } } // Process subsequent rows from 1 to m-1 for (int i = 1; i < m; i++) { // First, update the first column of the current row long[] tempCol0 = new long[MAX_XOR_VAL]; int firstColVal = grid[i][0]; for (int x = 0; x < MAX_XOR_VAL; x++) { if (dp[0][x] > 0) { tempCol0[x ^ firstColVal] = dp[0][x]; } } dp[0] = tempCol0; // Update the rest of the columns for the current row for (int j = 1; j < n; j++) { long[] newCounts = new long[MAX_XOR_VAL]; int currentVal = grid[i][j]; for (int x = 0; x < MAX_XOR_VAL; x++) { long fromUp = dp[j][x]; // from (i-1, j) long fromLeft = dp[j - 1][x]; // from (i, j-1) newCounts[x ^ currentVal] = (fromUp + fromLeft) % MOD; } dp[j] = newCounts; } } return (int) dp[n - 1][k]; } } ``` ### Algorithm - The core logic is the same as the standard DP, but we optimize space. - Instead of a 3D table `dp[m][n][C]`, we use a 2D table `dp[n][C]`. - `dp[j][x]` will store the number of paths to the cell in the *current* row `i` at column `j` with an XOR sum of `x`. - **Initialization**: Initialize `dp` for the first row (`i=0`). `dp[0][grid[0][0]] = 1`. Then for `j` from 1 to `n-1`, compute `dp[j]` based on `dp[j-1]`. - **Iteration**: For each subsequent row `i` from 1 to `m-1`: - The values in `dp` currently represent the counts for row `i-1`. - First, update `dp[0]` for the current row `i`. This only depends on the `dp[0]` from the previous row. - Then, for `j` from 1 to `n-1`, update `dp[j]`. The new `dp[j]` is calculated based on the old `dp[j]` (paths from above) and the new `dp[j-1]` (paths from the left). - **Result**: After iterating through all rows, the answer is `dp[n-1][k]`.