We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Moving Stones Until Consecutive

Number: 1103

Difficulty: Medium

Paid? No

Companies: Meta

Problem Description

Given three stones placed at distinct positions on the X-axis, determine the minimum and maximum number of moves needed such that the stones are in three consecutive positions. In each move, you can move a stone that is at one of the endpoints (either the lowest or highest positioned stone) to a new position between the current endpoints, provided that the new position is not already occupied by the middle stone.

Key Insights

  • Sort the three positions to simplify the gap calculations.
  • The game ends when the stones are in consecutive positions (i.e., the difference between adjacent stones is 1).
  • The minimum moves have special cases:
    • 0 moves if the stones are already consecutive.
    • 1 move if there is a gap of exactly 2 between any two stones.
    • Otherwise, 2 moves are required.
  • The maximum moves is computed by taking the larger gap between the two pairs (left gap and right gap) minus 1.

Space and Time Complexity

Time Complexity: O(1) - The solution only involves a few arithmetic operations. Space Complexity: O(1) - A constant amount of extra space is used.

Solution

The approach begins by sorting the positions of the three stones to obtain x, y, and z where x < y < z. Two primary cases are considered for minimum moves:

  1. If the stones are already consecutive (gaps of 1), no moves are needed.
  2. If one gap is exactly 2, then a single move is sufficient because the stone can be moved to fill the gap.
  3. Otherwise, the answer for minimum moves is 2.

For the maximum number of moves, the key observation is that each move reduces one of the larger gaps by one position. Thus, the maximum moves are equal to the larger gap (either between x and y or between y and z) minus 1.

This solution uses simple sorting and arithmetic to achieve optimal performance.

Code Solutions

# Python solution for Moving Stones Until Consecutive

def movingStones(a, b, c):
    # Sort the positions in ascending order
    x, y, z = sorted([a, b, c])
    
    # Check for the minimum moves based on the gaps
    if z - x == 2:  # stones are consecutive
        min_moves = 0
    elif (y - x == 2) or (z - y == 2):
        # One gap is exactly 2 means one move can fill the gap
        min_moves = 1
    else:
        # Otherwise, two moves are needed
        min_moves = 2
    
    # The maximum moves equals the larger gap between adjacent stones minus 1
    max_moves = max(y - x, z - y) - 1
    
    return [min_moves, max_moves]

# Example usage:
print(movingStones(1, 2, 5))   # Output: [1, 2]
print(movingStones(4, 3, 2))   # Output: [0, 0]
print(movingStones(3, 5, 1))   # Output: [1, 2]
← Back to All Questions