Moving Stones Until Consecutive - Practice Coding Problems

Moving Stones Until Consecutive - Problem

Math Brainteaser Medium

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 array answer of length 2 where:

answer[0] is the minimum number of moves you can play
answer[1] is the maximum number of moves you can play

Input & Output

Example 1 — Basic Case

$ Input: a = 1, b = 2, c = 5

› Output: [1, 2]

💡 Note: Sorted positions: [1, 2, 5]. Gap between 2 and 5 is 2 spaces. Min: move stone at 5 to position 3 in 1 move. Max: fill gap by moving stones one by one, taking 2 moves total.

Example 2 — Already Close to Consecutive

$ Input: a = 4, b = 3, c = 2

› Output: [0, 0]

💡 Note: Sorted positions: [2, 3, 4]. Already consecutive! No moves needed, so both min and max are 0.

Example 3 — Large Gaps

$ Input: a = 1, b = 9, c = 2

› Output: [2, 7]

💡 Note: Sorted positions: [1, 2, 9]. Large gap of 6 between 2 and 9. Min: need 2 moves to make consecutive. Max: can make 7 moves by filling the gap gradually.

Constraints

1 ≤ a, b, c ≤ 100
a, b, c are distinct integers

Visualization

Tap to expand

Understanding the Visualization

Input

Three stones at positions a, b, c

Process

Move endpoint stones to fill gaps

Output

[minimum moves, maximum moves] to make consecutive

Key Takeaway

🎯 Key Insight: Analyze gaps between sorted positions to determine move counts mathematically

Asked in

G Google 12 f Facebook 8

The key insight is analyzing gaps between sorted stone positions. For minimum moves: 0 if already consecutive (gap=2), 1 if one stone can fix it, otherwise 2. For maximum moves: take the larger gap between adjacent stones. Best approach uses mathematical formulas with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(2^n)	O(n)	Simulate all possible move sequences to find min and max
Mathematical Analysis	O(1)	O(1)	Use mathematical formulas based on gap analysis

Brute Force Simulation — Algorithm Steps

Sort positions to get x < y < z
Recursively try moving x or z to all valid positions
Track minimum and maximum moves to reach consecutive state

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with three stones at given positions

Try Moves

Recursively try moving leftmost or rightmost stone

Find Min/Max

Track shortest and longest paths to consecutive positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

void solution(int a, int b, int c, int* result) {
    int positions[3] = {a, b, c};
    
    // Sort positions
    for (int i = 0; i < 2; i++) {
        for (int j = i + 1; j < 3; j++) {
            if (positions[i] > positions[j]) {
                int temp = positions[i];
                positions[i] = positions[j];
                positions[j] = temp;
            }
        }
    }
    
    int x = positions[0], y = positions[1], z = positions[2];
    
    // Min moves calculation
    int minMoves;
    if (z - x == 2) {
        minMoves = 0;
    } else if (y - x <= 2 || z - y <= 2) {
        minMoves = 1;
    } else {
        minMoves = 2;
    }
    
    // Max moves calculation
    int maxMoves = (y - x - 1) > (z - y - 1) ? (y - x - 1) : (z - y - 1);
    
    result[0] = minMoves;
    result[1] = maxMoves;
}

int main() {
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    int result[2];
    solution(a, b, c, result);
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Exponential branching factor as we try all possible moves recursively

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth proportional to number of moves

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler