You are standing in a 2D grid at (0,0) . You need to go to (x,y) . In one move you can go from (a,b) to (c,d) if:

1. c and d are integers
2. |a-c| |b-d|=K (K is provided in the input)

Find if it is possible to reach final destination . If possible what is the minimum number of moves you can take to reach the final destination?

CONSTRAINTS: -10^5<=x,y<=10^5 1<=K<=10^9

Eg- INPUT K=5 X=1, Y=3

OUTPUT 2 [(0,0)->(-3,2)->(1,3)]

In the first move, one can go from (0,0) to (-3,2) (|0-(-3)| (0-2) = 3 2 = 5) and second move, (-3,2) to (1,3) (|-3-1| |2-3| = 4 1 = 5)

Hence 2.

CodePudding user response：

The comments asserted a necessary criterion, that 2 must divide |x| |y| at least as many times as it divides k. You should prove it.

But now suppose that P is a path from (0, 0) to (x, y). Let's let P_h be the sum of the lengths of the horizontal steps you take. Similarly let P_v be the sum of the lengths of the vertical steps you take. The following are easy to show:

1. |x| ≤ P_h
2. 2 divides P_h - |x|
3. |y| ≤ P_v
4. 2 divides P_v - |y|
5. k divides P_h P_v and in fact the number of steps taken is (P_h P_v)/k.

Between these facts, if i*k is the first multiple of k which is at least |x| |y| with i*k - |x| - |y| even, then any path of length i*k must be minimal.

To finish, show that you can always construct a path of that length. And then the problem becomes easy.

CodePudding user response：

Constant time solution.

All distances here are Manhattan distances.

Everything a distance of k from the origin can be reached in one step. This forms a diamond shape.

Within that diamond, every tile an even distance from the origin can be reached in 2 steps.

If k is odd, then every tile in the diamond an odd distance from the origin can be reached in 3 steps. If k is even then these tiles can't be reached.

Let's call (x, y) the target. The target can be reached unless k is even and |x| |y| is odd.

If the target is inside the diamond, determine whether it can be reached in 0, 1, 2, or 3 based on the rules above.

If the target is outside the diamond, find the distance between the target and the closest corner (closest of (-k,0), (k,0), (0,-k), (0,k)). Call this d.

If d%k == 0 then it takes d/k moves to get to the corner, 1 to get to the center. Otherwise, after reaching the corner, we have a remaining distance of d%k to move. If this is even we can stay along the edge of the diamond where we have one additional move to get to the origin. If this is odd then k must also be odd and we can be adjacent to the edge of the diamond where there are two moves to the origin.

Here's some Ruby code that implements this.

def get_moves(x, y, k)
  distance = get_dist(0, 0, x, y)

  # return 0 to 3 for reachable distances inside the diamond
  # return -1 for unreachable distances
  return -1 if k % 2 == 0 && distance % 2 == 1
  return 0 if distance == 0
  return 1 if distance == k
  return 2 if distance < k && distance % 2 == 0
  return 3 if distance < k && distance % 2 == 1
  
  # Find the distance between the target & nearest corner of the diamond
  distance_to_corner = [get_dist(x, y, 0, -k), get_dist(x, y, 0, k), get_dist(x, y, -k, 0), get_dist(x, y, k, 0)].min

  # Find the extra distance since we're going in steps of size k
  extra_distance = (k - distance_to_corner % k) % k
  
  # If the extra distance is even then we can stay along the
  # edge of the diamond which is 1 move from the origin.
  # Otherwise we're adjacent to the edge of the diamond,
  # putting us 2 moves from the origin.
  if extra_distance % 2 == 0
    return 1   (distance_to_corner   extra_distance) / k
  else
    return 2   (distance_to_corner   extra_distance) / k
  end
end

def get_dist(x_1, y_1, x_2, y_2)
  return (x_2 - x_1).abs   (y_2 - y_1).abs
end