Count Paths With the Given XOR Value - Practice Coding Problems

Count Paths With the Given XOR Value - 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 10⁹ + 7.

Input & Output

Example 1 — Basic 2x2 Grid

$ Input: grid = [[5,2],[1,6]], k = 1

› Output: 1

💡 Note: There are two paths: 5→2→6 (XOR = 5⊕2⊕6 = 1) and 5→1→6 (XOR = 5⊕1⊕6 = 2). Only the first path has XOR equal to k=1.

Example 2 — No Valid Paths

$ Input: grid = [[1,2],[3,4]], k = 10

› Output: 0

💡 Note: The two paths are: 1→2→4 (XOR = 1⊕2⊕4 = 7) and 1→3→4 (XOR = 1⊕3⊕4 = 6). Neither equals k=10.

Example 3 — Single Cell

$ Input: grid = [[7]], k = 7

› Output: 1

💡 Note: Only one path exists containing just the single cell. XOR = 7, which equals k=7.

Constraints

1 ≤ m, n ≤ 300
0 ≤ grid[i][j] ≤ 15
0 ≤ k ≤ 15

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with values, target XOR value k

Find Paths

Only move right or down, track XOR along path

Count Valid

Return count of paths where XOR equals k

Key Takeaway

🎯 Key Insight: Use dynamic programming to track path counts for each XOR value at every position

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to track XOR values as we build paths, not after completion. The optimal approach uses dynamic programming with a 3D table dp[i][j][xor] to count paths efficiently. Time: O(m×n×1024), Space: O(m×n×1024)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(m×n×1024)	O(m×n×1024)	Build solution bottom-up using 3D DP table
Recursive with Memoization	O(m×n×1024)	O(m×n×1024)	Cache results to avoid recomputing same states
Recursive Brute Force	O(2^(m+n))	O(m+n)	Try all possible paths using recursion and count valid ones

Dynamic Programming — Algorithm Steps

Create 3D DP table: dp[row][col][xor_value]
Initialize base case: dp[0][0][grid[0][0]] = 1
Fill table: for each cell, update from left and top neighbors
Return dp[m-1][n-1][k] as final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0][0][grid[0][0]] = 1

Fill Table

For each cell, sum paths from top and left

Result

Answer is dp[m-1][n-1][k]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int solution(int** grid, int m, int n, int k) {
    // Allocate 3D DP array
    int*** dp = (int***)malloc(m * sizeof(int**));
    for (int i = 0; i < m; i++) {
        dp[i] = (int**)malloc(n * sizeof(int*));
        for (int j = 0; j < n; j++) {
            dp[i][j] = (int*)calloc(1024, sizeof(int));
        }
    }
    
    // Base case
    dp[0][0][grid[0][0]] = 1;
    
    // Fill the DP table
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            
            for (int xorVal = 0; xorVal < 1024; xorVal++) {
                // From top
                if (i > 0) {
                    int prevXor = xorVal ^ grid[i][j];
                    dp[i][j][xorVal] = (dp[i][j][xorVal] + dp[i-1][j][prevXor]) % MOD;
                }
                
                // From left
                if (j > 0) {
                    int prevXor = xorVal ^ grid[i][j];
                    dp[i][j][xorVal] = (dp[i][j][xorVal] + dp[i][j-1][prevXor]) % MOD;
                }
            }
        }
    }
    
    int result = dp[m-1][n-1][k];
    
    // Free memory
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            free(dp[i][j]);
        }
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    int m = 2, n = 2;
    int** grid = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Example: grid = [[5,2],[1,6]], k = 1
    grid[0][0] = 5; grid[0][1] = 2;
    grid[1][0] = 1; grid[1][1] = 6;
    int k = 1;
    
    printf("%d\n", solution(grid, m, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×1024)

Three nested loops: m rows, n columns, 1024 possible XOR values

✓ Linear Growth

Space Complexity

O(m×n×1024)

3D DP table stores count for each position and XOR value

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler