Welcome to Subscribe On Youtube

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)$.

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

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

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


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


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

All Problems

All Solutions