We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Paths With the Given XOR Value

Difficulty: Medium

Problem Description

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^9 + 7.

Key Insights

  • The problem involves finding paths on a grid with specific movement constraints (right and down).
  • The XOR operation is applied across the values in the grid, and only paths that result in a specific XOR value (k) are counted.
  • Dynamic programming can be utilized to store intermediate results, particularly the number of ways to reach each cell with a specific XOR value.
  • The constraints on the values (0 to 15) and k (0 to 15) suggest a feasible solution using a combination of dynamic programming and bit manipulation.

Space and Time Complexity

Time Complexity: O(m * n * k)
Space Complexity: O(m * n * k)

Solution

We can use a dynamic programming approach to solve this problem. We will maintain a 3D DP array where dp[i][j][x] represents the number of ways to reach cell (i, j) with an XOR value of x.

  1. Initialize a DP table with dimensions [m][n][16] (since values and k are between 0 and 15).
  2. Set dp[0][0][grid[0][0]] = 1 since the starting point must match its own value.
  3. Iterate over all cells in the grid. For each cell, consider moving right and down:
    • For each possible XOR value computed so far, update the DP table for the next cell by XORing the current cell's value.
  4. Finally, sum the values in dp[m-1][n-1][k] to get the total number of valid paths.

Code Solutions

def countPaths(grid, k):
    MOD = 10**9 + 7
    m, n = len(grid), len(grid[0])
    dp = [[[0] * 16 for _ in range(n)] for _ in range(m)]
    
    dp[0][0][grid[0][0]] = 1
    
    for i in range(m):
        for j in range(n):
            for x in range(16):
                if dp[i][j][x] > 0:
                    if i + 1 < m:  # Move down
                        dp[i + 1][j][x ^ grid[i + 1][j]] = (dp[i + 1][j][x ^ grid[i + 1][j]] + dp[i][j][x]) % MOD
                    if j + 1 < n:  # Move right
                        dp[i][j + 1][x ^ grid[i][j + 1]] = (dp[i][j + 1][x ^ grid[i][j + 1]] + dp[i][j][x]) % MOD
    
    return dp[m - 1][n - 1][k]
← Back to All Questions