Skip to content

3996. Even Number of Knight Moves

Description

You are given two integer arrays start and target, where each array is of the form [x, y] representing a cell on a standard 8 x 8 chessboard.

Return true if a knight can move from start to target in an even number of moves. Otherwise, return false.

Note: A valid knight move consists of moving two squares in one direction and one square perpendicular to it. The figure below illustrates all eight possible moves from a cell.

Β 

Example 1:

Input: start = [1,1], target = [2,2]

Output: true

Explanation:

One possible sequence of moves is (1, 1) -> (3, 2) -> (2, 4) -> (4, 3) -> (2, 2).

The knight reaches the target in 4 moves, which is even. Thus, the answer is true.

Example 2:

Input: start = [4,5], target = [6,6]

Output: false

Explanation:​​​​​​​

It is impossible to reach target = [6, 6] from start = [4, 5] in an even number of moves. Thus, the answer is false.

Β 

Constraints:

  • start.length == target.length == 2
  • 0 <= start[i], target[i] <= 7

Solutions

Solution 1: Parity

Each knight move has an offset of \((\pm 1, \pm 2)\) or \((\pm 2, \pm 1)\), so the change in the coordinate sum \(x + y\) is always odd. In other words, every move flips the color of the square (black/white distinguished by \((x + y) \bmod 2\)).

Therefore:

  • After an even number of moves, the start and target have the same color;
  • After an odd number of moves, the start and target have different colors.

On an \(8 \times 8\) chessboard, a knight can reach any square, and any path to a same-color square must have even length. Hence, it suffices to check whether \((x + y) \bmod 2\) is equal for the start and the target.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
class Solution:
    def canReach(self, start: list[int], target: list[int]) -> bool:
        return (start[0] + start[1]) % 2 == (target[0] + target[1]) % 2

1
2
3
4
5
class Solution {
    public boolean canReach(int[] start, int[] target) {
        return (start[0] + start[1]) % 2 == (target[0] + target[1]) % 2;
    }
}

1
2
3
4
5
6
class Solution {
public:
    bool canReach(vector<int>& start, vector<int>& target) {
        return (start[0] + start[1]) % 2 == (target[0] + target[1]) % 2;
    }
};

1
2
3
func canReach(start []int, target []int) bool {
    return (start[0]+start[1])%2 == (target[0]+target[1])%2
}

1
2
3
function canReach(start: number[], target: number[]): boolean {
    return (start[0] + start[1]) % 2 === (target[0] + target[1]) % 2;
}

Comments