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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Paths With the Given XOR Value

Number: 3659

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an m x n grid of integers (each between 0 and 15) and an integer k (also between 0 and 15), count the number of paths from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) (moving only right or down) such that the XOR of all numbers in the path equals k. The answer should be returned modulo 10^9 + 7.

Key Insights

  • Use dynamic programming with an extra state for the cumulative XOR.
  • Because grid values and k are small (<16), the XOR state space is limited to 16 possible values.
  • For each cell, the cumulative XOR value can be updated from the top or left neighbor.
  • An iterative DP approach is used, ensuring modulo operations are applied to keep numbers in range.
  • Direct use of a 3D DP (or a 2D DP with XOR dimension) is computationally feasible.

Space and Time Complexity

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

Solution

We solve the problem using dynamic programming. The idea is to define a state dp[i][j][x] representing the number of ways to reach cell (i, j) such that the accumulated XOR is x. The transitions are straightforward: from the top (if available) and from the left (if available), update the XOR value by taking the XOR of the current cell's value with the previous state's XOR value. Finally, the answer is dp[m-1][n-1][k] modulo 10^9 + 7.

Data Structures:

  • A 3-dimensional list/array for DP, where the first two dimensions represent the cell coordinates and the third represents the possible XOR values (0 to 15).

Algorithmic Approach:

  1. Initialize dp[0][0][grid[0][0]] = 1.
  2. Iterate over each cell in the grid.
  3. From each valid previous cell (top and left), update the current cell's DP state using the formula: new_xor = previous_xor XOR grid[i][j].
  4. Sum up the number of ways modulo 10^9 + 7.
  5. Return dp[m-1][n-1][k] modulo 10^9 + 7.

Important Notes:

  • The key trick is recognizing that XOR operations are reversible and the value domain (0-15) is small, allowing for tractable state space.
  • Always perform modulo operations to prevent overflow.

Code Solutions

# Python solution for "Count Paths With the Given XOR Value"

MOD = 10**9 + 7

def countPaths(grid, k):
    m = len(grid)
    n = len(grid[0])
    # dp[i][j][x] represents number of ways to obtain XOR value x at cell (i, j)
    dp = [[[0] * 16 for _ in range(n)] for _ in range(m)]
    
    # Initialize the top-left cell with its own value
    dp[0][0][grid[0][0]] = 1
    
    for i in range(m):
        for j in range(n):
            # Avoid re-initializing the starting cell.
            # For every cell, try to move right and down with current XOR values.
            for xor_val in range(16):
                ways = dp[i][j][xor_val]
                if ways:
                    # Move Down if within bounds
                    if i + 1 < m:
                        new_xor = xor_val ^ grid[i+1][j]
                        dp[i+1][j][new_xor] = (dp[i+1][j][new_xor] + ways) % MOD
                    # Move Right if within bounds
                    if j + 1 < n:
                        new_xor = xor_val ^ grid[i][j+1]
                        dp[i][j+1][new_xor] = (dp[i][j+1][new_xor] + ways) % MOD
    
    # Return the number of paths with XOR equal to k at bottom-right cell.
    return dp[m-1][n-1][k]

# Example usage:
# grid = [[2, 1, 5], [7, 10, 0], [12, 6, 4]]
# k = 11
# print(countPaths(grid, k))  # Output: 3
← Back to All Questions