SDE - 1

You are given an infinite chessboard (ie: the x-coordinates and y-coordinates can be anything between -infinity to +infinity).

You have a knight placed at coordinates ‘(0, 0)’. Find the minimum number of steps needed to move the knight to ‘(X, Y)’.

The knight has 8 possible moves, each move is two units in a cardinal direction, then one unit in an orthogonal direction.

For example :

As depicted in the photo below, the knight currently at (0, 0) can move to any of the 8 positions: (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2).

Example :

If X = 1 and Y = -1, then we need to find out the minimum number of steps to move the knight from (0, 0) to (1, -1).

We need at least 2 steps to move the knight to the desired position.

First move: (0, 0) -> (2, 1) 

Second move: (2,1) -> (1, -1)

Here we can see that there are many ways, but we need at least 2 steps. Therefore we will return the value 2.

You have been given a square chessboard of size ‘N x N’. The position coordinates of the Knight and the position coordinates of the target are also given.

Your task is to find out the minimum steps a Knight will take to reach the target position.

Example:

knightPosition: {3,4}
targetPosition: {2,1}

The knight can move from position (3,4) to positions (1,3), (2,2) and (4,2). Position (4,2) is selected and the ‘stepCount’ becomes 1. From position (4,2), the knight can directly jump to the position (2,1) which is the target point and ‘stepCount’ becomes 2 which is the final answer. 

Note:

1. The coordinates are 1 indexed. So, the bottom left square is (1,1) and the top right square is (N, N).

2. The knight can make 8 possible moves as given in figure 1.

3. A Knight moves 2 squares in one direction and 1 square in the perpendicular direction (or vice-versa).

You live in a Ninja town which is in the form of a N * M grid. In this town, people travel from one place to another by jumping over the buildings which are present in each cell of the grid. It is Christmas eve, and Santa wants to give gifts and chocolates to the kids who live in the building which is present at the cell (N - 1, M - 1). Initially, Santa is present on cell (0, 0). Since Santa is in a hurry, help him find a path from starting point to the endpoint with the least amount of time.

The Santa may go only from one building to any of its adjacent buildings which is present either to the right or to the bottom or bottom right cell i.e. if the current position is (x, y), he may go to (x + 1, y + 1) or (x + 1, y) or (x, y + 1) given that the new coordinates are in the grid. The time taken to reach from one building to another is equal to the absolute difference between the heights of buildings.

Note:

1. The heights of the buildings are positive.
2. Santa starts from the cell (0, 0) and he has to reach the building (N - 1, M - 1).
3. Santa cannot leave the grid at any point of time.

How to design Splitwise