Problem

There are three stones in different positions on the X-axis. You are given three integers a, b, and c, the positions of the stones.

In one move, you pick up a stone at an endpoint (i.e., either the lowest or highest position stone), and move it to an unoccupied position between those endpoints. Formally, let’s say the stones are currently at positions x, y, and z with x < y < z. You pick up the stone at either position x or position z, and move that stone to an integer position k, with x < k < z and k != y.

The game ends when you cannot make any more moves (i.e., the stones are in three consecutive positions).

Return an integer arrayanswer of length2 where :

  • answer[0] is the minimum number of moves you can play, and
  • answer[1] is the maximum number of moves you can play.

Examples

Example 1

1
2
3

Input: a = 1, b = 2, c = 5
Output: [1,2]
Explanation: Move the stone from 5 to 3, or move the stone from 5 to 4 to 3.

Example 2

1
2
3

Input: a = 4, b = 3, c = 2
Output: [0,0]
Explanation: We cannot make any moves.

Example 3

1
2
3

Input: a = 3, b = 5, c = 1
Output: [1,2]
Explanation: Move the stone from 1 to 4; or move the stone from 1 to 2 to 4.

Constraints

  • 1 <= a, b, c <= 100
  • a, b, and c have different values.

Solution

Method 1 -

Intuition

Sort the positions. The minimum moves depend on the gaps: if the stones are already consecutive, 0 moves; if one gap is 1 or 2, only 1 move; otherwise, 2 moves. The maximum moves is the sum of the gaps minus 2.

Approach

Sort a, b, c to get x < y < z. Compute left_gap = y - x, right_gap = z - y. If both gaps are 1, return [0,0]. If either gap is 2, min moves is 1. Otherwise, min moves is 2. Max moves is left_gap - 1 + right_gap - 1.

Code

1
2
3
4
5
6
7
8
9

vector<int> numMovesStones(int a, int b, int c) {
    vector<int> v = {a, b, c};
    sort(v.begin(), v.end());
    int x = v[0], y = v[1], z = v[2];
    int left = y - x, right = z - y;
    int min_moves = (left == 1 && right == 1) ? 0 : (left <= 2 || right <= 2) ? 1 : 2;
    int max_moves = left - 1 + right - 1;
    return {min_moves, max_moves};
}
1
2
3
4
5
6
7
8
9

public int[] numMovesStones(int a, int b, int c) {
    int[] v = {a, b, c};
    Arrays.sort(v);
    int x = v[0], y = v[1], z = v[2];
    int left = y - x, right = z - y;
    int min_moves = (left == 1 && right == 1) ? 0 : (left <= 2 || right <= 2) ? 1 : 2;
    int max_moves = left - 1 + right - 1;
    return new int[]{min_moves, max_moves};
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

Complexity

  • ⏰ Time complexity: O(1) (sorting 3 numbers is constant time).
  • 🧺 Space complexity: O(1).