1033. Moving Stones Until Consecutive
brainteaser, Math, AMateList ·Problem Statement
link: LeetCode.cn LeetCode 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, and answer[1] is the maximum number of moves you can play.
Example:
Input: a = 1, b = 2, c = 5
Output: [1,2]
Input: a = 4, b = 3, c = 2
Output: [0,0]
Input: a = 3, b = 5, c = 1
Output: [1,2]
Constraints: 1 <= a, b, c <= 100 a, b, and c have different values.
Solution Approach
The solution involves sorting the three stone positions and then calculating the minimum and maximum moves based on the gaps between the sorted positions, considering special cases where the stones are already close together or far apart.
Algorithm
- Sorting the Positions: Start by sorting the stone positions to get them in order, which allows for easier calculation of the gaps between them.
- Calculating Minimum Moves: Determine the minimum number of moves based on the gaps between the sorted stones. If the stones are already consecutive, no moves are needed; if two stones are one position apart, only one move is required.
- Calculating Maximum Moves: The maximum number of moves is determined by moving each stone towards the middle until they are consecutive, which can be done by filling the largest gaps first.
Implement
class Solution:
def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
x, y, z = sorted([a, b, c])
res = [2, z - x - 2]
if ((z - y) == 1 and (y - x) == 1):
res[0] = 0
elif ((z - y) <= 2 or (y - x) <= 2):
res[0] = 1
return res