Domain 1EasyCORE

Moving Stones Until Consecutive

The problem involves three stones placed on a number line at positions `a`, `b`, and `c`. The goal is to move the stones so that they are in consecutive positions. Each turn, you can pick up a stone from either endpoint (the lowest or highest position) and move it to an unoccupied position between the other two stones. The game ends when no more moves can be made, i.e., the stones are in consecutive positions.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Brainteaser

1033. Moving Stones Until Consecutive

Model: qwen2.5-coder:14b
Topics: Brainteaser
FAANG asked: 1
Acceptance rate: 43.3%


Problem Breakdown

The problem involves three stones placed on a number line at positions a, b, and c. The goal is to move the stones so that they are in consecutive positions. Each turn, you can pick up a stone from either endpoint (the lowest or highest position) and move it to an unoccupied position between the other two stones. The game ends when no more moves can be made, i.e., the stones are in consecutive positions.

Inputs:

  • Three integers a, b, and c representing the initial positions of the stones on the number line.

Outputs:

  • An array [minimum_moves, maximum_moves] where:
    • minimum_moves is the fewest number of moves required to make the stones consecutive.
    • maximum_moves is the most number of moves required to make the stones consecutive.

Implicit Constraints or Tricky Edge Cases:

  • The positions are distinct (a != b, b != c, c != a).
  • Positions are within the range [1, 100].
  • If the stones are already consecutive, both minimum_moves and maximum_moves should be 0.

Intuition

The brute-force approach would involve simulating all possible moves until the stones are consecutive. However, this is inefficient due to the potential for many unnecessary moves and high time complexity.

A better approach involves understanding the gaps between the stones:

  • If there is a gap of 1 or 2 between any two stones, only one move is needed.
  • If there is a larger gap, multiple moves are required, but the number of moves can be determined by the size of the gap.

The key insight is that moving a stone from an endpoint to fill a small gap (size 1 or 2) requires fewer moves than filling a larger gap.

Approach

  1. Sort the Positions: First, sort the positions a, b, and c so that x < y < z.
  2. Calculate Gaps: Compute the gaps between consecutive stones: gap1 = y - x - 1 and gap2 = z - y - 1.
  3. Determine Minimum Moves:
    • If either gap is 0, it means the stones are already consecutive (minimum_moves = 0).
    • If both gaps are 1, only one move is needed to make them consecutive (minimum_moves = 1).
    • If there is at least one gap of size 2 or more and another gap of size 1, one move is sufficient (minimum_moves = 1).
    • Otherwise, two moves are required (minimum_moves = 2).
  4. Determine Maximum Moves:
    • The maximum number of moves is simply the sum of the gaps (maximum_moves = gap1 + gap2).

Complexity Analysis

  • Time Complexity: O(1) because sorting three numbers and calculating a few differences are constant-time operations.
  • Space Complexity: O(1) as no additional space proportional to input size is used.

Solution

def numMovesStones(a: int, b: int, c: int) -> List[int]:
    # Sort the positions
    x, y, z = sorted([a, b, c])
    
    # Calculate gaps
    gap1 = y - x - 1
    gap2 = z - y - 1
    
    # Determine minimum moves
    if gap1 == 0 and gap2 == 0:
        min_moves = 0
    elif gap1 <= 1 or gap2 <= 1:
        min_moves = 1
    else:
        min_moves = 2
    
    # Maximum moves is the sum of gaps
    max_moves = gap1 + gap2
    
    return [min_moves, max_moves]

Edge Cases Handled

  • Already Consecutive: If a, b, and c are already consecutive (e.g., a=1, b=2, c=3), the function returns [0, 0].
  • Single Move Needed: If there is a gap of size 1 or 2 between any two stones (e.g., a=1, b=3, c=4), the function returns [1, 2].
  • Two Moves Needed: If both gaps are larger than 2 (e.g., a=1, b=5, c=8), the function returns [2, 7].

The solution provided is correct, efficient, and clear. The approach correctly handles all edge cases and provides a straightforward way to determine the minimum and maximum number of moves required to make the stones consecutive.