Moving Stones Until Consecutive

medium math sorting simulation

Problem

Three stones sit at distinct integer positions a, b, c on a number line. In one move you take a stone from an endpoint position (the smallest or largest) and place it at any empty integer position strictly between the other two stones. The game ends when the three stones are consecutive (e.g. 4, 5, 6). Return the minimum and maximum number of moves.

Inputa = 1, b = 2, c = 5

Output[1, 2]

Min: move 5 → 3 to get 1, 2, 3 (one move). Max: move 5 → 4, then 1 → 3 (two moves).

def num_moves_stones(a, b, c):
    x, y, z = sorted([a, b, c])
    left = y - x - 1
    right = z - y - 1
    if left == 0 and right == 0:
        return [0, 0]
    mn = 1 if (left <= 1 or right <= 1) else 2
    mx = left + right
    return [mn, mx]

function numMovesStones(a, b, c) {
  const [x, y, z] = [a, b, c].sort((p, q) => p - q);
  const left = y - x - 1;
  const right = z - y - 1;
  if (left === 0 && right === 0) return [0, 0];
  const mn = (left <= 1 || right <= 1) ? 1 : 2;
  const mx = left + right;
  return [mn, mx];
}

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int[] s = { a, b, c };
        Arrays.sort(s);
        int left = s[1] - s[0] - 1;
        int right = s[2] - s[1] - 1;
        if (left == 0 && right == 0) return new int[]{ 0, 0 };
        int mn = (left <= 1 || right <= 1) ? 1 : 2;
        int mx = left + right;
        return new int[]{ mn, mx };
    }
}

vector<int> numMovesStones(int a, int b, int c) {
    int s[3] = { a, b, c };
    sort(s, s + 3);
    int left = s[1] - s[0] - 1;
    int right = s[2] - s[1] - 1;
    if (left == 0 && right == 0) return { 0, 0 };
    int mn = (left <= 1 || right <= 1) ? 1 : 2;
    int mx = left + right;
    return { mn, mx };
}

Explanation

The whole problem comes down to looking at the two empty gaps between the three stones. Once you sort the positions, everything else is just simple arithmetic — no simulation needed.

First sort the positions into x, y, z. The number of empty integer slots in the left gap is left = y - x - 1 and in the right gap is right = z - y - 1. If both gaps are 0, the stones are already consecutive, so the answer is [0, 0].

For the maximum, you fill one empty slot per move, so it is simply left + right. For the minimum, if either gap is 0 or 1, a single clever move closes everything up, giving 1; otherwise the closest stone needs 2 moves to slide in.

Example: a=1, b=2, c=5 sorts to x=1, y=2, z=5. Here left = 0 and right = 2. Since a gap is <= 1, min is 1, and max is 0 + 2 = 2, so the answer is [1, 2].

Because we only sort three numbers and do a few comparisons, this runs in constant time.

Time: O(1) Space: O(1)