Is Count Paths With the Given XOR Value easy or hard?

The problem is classified as Medium because it combines grid traversal with XOR state tracking. The main challenge is recognizing that the path state must include the current XOR value, which leads to a 3D dynamic programming solution.

Count Paths With the Given XOR Value Python/Java solution

Most solutions implement dynamic programming that propagates XOR states while moving right and down in the grid. The same logic works in Python, Java, C++, and Go by maintaining a DP table or memoization cache and updating XOR values at each transition.

How to solve Count Paths With the Given XOR Value in O(n)?

The problem cannot be solved in pure O(n) time because the state depends on both grid position and XOR value. The best practical solution is O(m * n * X) using dynamic programming, where each cell maintains counts for all reachable XOR states.

What is the best approach for Count Paths With the Given XOR Value?

Dynamic programming with a XOR state is the most effective approach. Track the number of ways to reach each cell with a specific XOR value using a 3D DP state (row, column, xor). This reduces the exponential search space to O(m * n * X), where X is the number of possible XOR values.

Is Count Paths With the Given XOR Value asked at Google/Amazon/Meta?

Matrix dynamic programming and XOR state problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving path counting with constraints or bitwise operations are especially common in system-level algorithm rounds.

What data structure is used in Count Paths With the Given XOR Value?

The core data structure is a dynamic programming table that stores counts for each cell and XOR state. Implementations typically use a 3D array or hash map keyed by (row, column, xor). Bit manipulation is used to update XOR values efficiently.

What is the time complexity of Count Paths With the Given XOR Value?

The optimal dynamic programming solution runs in O(m * n * X) time. The algorithm processes every cell in the grid and tracks possible XOR values that can appear at that position. Space complexity is also O(m * n * X) for storing intermediate states.

Description Hints 1 Video 12:18

3393. Count Paths With the Given XOR Value

Medium40.6% acceptance1 company

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.

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

Asked at 1 company

Microsoft

Topics

Hints open one at a time

Hint 1

Use DP.

3393. Count Paths With the Given XOR Value

Asked at 1 company

Topics

Hints open one at a time

Similar problems