The knight is the piece in the game of chess that, in one turn, can move two squares horizontally and one square vertically or two squares vertically and one square horizontally.
An infinite chessboard is given. All of its squares are empty except for the square with coordinates (0,0), where a knight stands.
Write a function:
def solution(A, B)
that, given two numbers A and B, returns the minimum number of turns required for the knight to move from square (0,0) to square (A,B). The function should return -1 if the knight cannot reach the given square. The function should return -2 if the required number of turns exceeds 100,000,000.
For example, given A=4 and B=5 the function should return 3, because the knight requires three turns to move from square (0,0) to square (4,5):
- in the first turn the knight moves from square (0,0) to square (2,1);
- in the second turn the knight moves from square (2,1) to square (3,3);
- in the thirs turn the knight moves from square (3,3) to square (4,5)
Assume that:
- A and B are integers within the range [-100,000,000...100,000,000]
Complexity:
- expected worst-case time complexity is O(1);
- expected worst-case space complexity is O(1).
function solution(A, B)
{
let dx = Math.abs(A);
let dy = Math.abs(B);
const limit = 100000000;
let moves = Math.max(Math.floor((dx+1)/2), Math.floor((dy+1)/2), Math.floor((dx+dy+2)/3));
while ((moves%2)!=(dx+dy)%2 && moves <= limit) moves++;
return moves <= limit ? moves : -2;
}