Problem Description

The "Moving Stones Until Consecutive" problem involves three stones placed at distinct positions on a number line. You are given three integers, a, b, and c, representing the positions of the stones. In each move, you can pick up the stone at the leftmost or rightmost position and move it to any position between the other two stones, as long as the stone does not land on a position already occupied by another stone.

Your goal is to find two things:

• The minimum number of moves required to make the stones' positions consecutive (i.e., so that their positions are x, x+1, and x+2 for some integer x).
• The maximum number of moves required to achieve the same.

Constraints:

• All positions a, b, c are distinct integers.
• The stones cannot occupy the same position after a move.
• Each move must involve the leftmost or rightmost stone.

Thought Process

At first glance, the problem seems to require simulating all possible moves, but since there are only three stones, we can reason about the possible configurations directly. The main challenge is to minimize and maximize the number of moves needed to make the stones consecutive.

For the minimum moves, we want to bring the stones together as quickly as possible. If two stones are already next to each other (i.e., the difference between their positions is 1), only one move is needed. If all stones are already consecutive, no moves are needed. If there is a gap of 2, we can also solve it in one move. Otherwise, two moves are required.

For the maximum moves, we always move the stone from one end towards the other, but only by one position at a time (never skipping over the middle stone), until all stones are consecutive. The maximum number of moves is simply the sum of the gaps between the stones, minus 2 (since the last move will bring the stones together).

Solution Approach

Here’s how we can solve the problem step by step:

1. Sort the positions: First, sort the stones’ positions so that a < b < c. This makes it easy to calculate the gaps between the stones.
2. Calculate the gaps: Compute left_gap = b - a and right_gap = c - b.
3. Determine the minimum moves:
   • If both gaps are 1 (i.e., the stones are already consecutive), then 0 moves are needed.
   • If either gap is 2 (i.e., the stones are like [1, 2, 4]), then 1 move is needed (move the far stone to fill the gap).
   • Otherwise, 2 moves are needed (move each far stone closer by one position).
4. Determine the maximum moves:
   • For each gap, the maximum moves is left_gap - 1 + right_gap - 1, since we can only move the end stones one step at a time.

We use simple arithmetic and conditional logic instead of brute-force simulation, making the solution efficient and easy to understand.

Example Walkthrough

Let's walk through a sample input: a = 1, b = 2, c = 5.

1. Sort the positions: [1, 2, 5]
2. Calculate gaps: left_gap = 2 - 1 = 1, right_gap = 5 - 2 = 3
3. Minimum moves:
   • left_gap is 1, right_gap is 3. Neither is 2, and not both are 1. So, minimum moves = 1 (since one gap is 2 or more, but one is 1).
4. Maximum moves:
   • (left_gap - 1) + (right_gap - 1) = (1 - 1) + (3 - 1) = 0 + 2 = 2
5. After the first move, move stone at position 5 to position 3: [1, 2, 3]. Now all stones are consecutive.

So, the minimum moves are 1, and the maximum moves are 2.

Time and Space Complexity

Brute-force Approach:

• Would involve simulating all possible moves, which grows rapidly with the number of stones and positions. For three stones, it is feasible but inefficient.
• Time Complexity: O(1) (since only three stones), but not scalable.
• Space Complexity: O(1)

• Sorting three numbers: O(1)
• Gap calculation and logic: O(1)
• Space Complexity: O(1)

The optimized approach is constant time and space because the number of stones is always three.

Summary

The "Moving Stones Until Consecutive" problem is elegantly solved by sorting the stones, calculating the gaps, and applying simple conditional logic to determine the minimum and maximum moves. The key insight is recognizing that, with only three stones, all possible configurations can be reasoned about directly without simulation. This leads to a constant-time solution that is both efficient and easy to implement.

Code Implementation

def numMovesStones(a: int, b: int, c: int):
    x, y, z = sorted([a, b, c])
    left_gap = y - x
    right_gap = z - y

    # Minimum moves
    if left_gap == 1 and right_gap == 1:
        min_moves = 0
    elif left_gap <= 2 or right_gap <= 2:
        min_moves = 1
    else:
        min_moves = 2

    # Maximum moves
    max_moves = (left_gap - 1) + (right_gap - 1)
    return [min_moves, max_moves]
      

#include <vector>
#include <algorithm>
using namespace std;

vector<int> numMovesStones(int a, int b, int c) {
    int x = min(a, min(b, c));
    int z = max(a, max(b, c));
    int y = a + b + c - x - z;
    int left_gap = y - x;
    int right_gap = z - y;
    int min_moves, max_moves;
    if (left_gap == 1 && right_gap == 1) {
        min_moves = 0;
    } else if (left_gap <= 2 || right_gap <= 2) {
        min_moves = 1;
    } else {
        min_moves = 2;
    }
    max_moves = (left_gap - 1) + (right_gap - 1);
    return {min_moves, max_moves};
}
      

import java.util.Arrays;

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int[] arr = {a, b, c};
        Arrays.sort(arr);
        int left_gap = arr[1] - arr[0];
        int right_gap = arr[2] - arr[1];
        int min_moves, max_moves;
        if (left_gap == 1 && right_gap == 1) {
            min_moves = 0;
        } else if (left_gap <= 2 || right_gap <= 2) {
            min_moves = 1;
        } else {
            min_moves = 2;
        }
        max_moves = (left_gap - 1) + (right_gap - 1);
        return new int[]{min_moves, max_moves};
    }
}
      

function numMovesStones(a, b, c) {
    let arr = [a, b, c].sort((x, y) => x - y);
    let left_gap = arr[1] - arr[0];
    let right_gap = arr[2] - arr[1];
    let min_moves, max_moves;
    if (left_gap === 1 && right_gap === 1) {
        min_moves = 0;
    } else if (left_gap <= 2 || right_gap <= 2) {
        min_moves = 1;
    } else {
        min_moves = 2;
    }
    max_moves = (left_gap - 1) + (right_gap - 1);
    return [min_moves, max_moves];
}