Gather Tokens on One Square
EasyGreedy
Problem
Tokens sit on squares of an infinite board line; positions[i] is the square of token i (several tokens may share a square).
You may move one token two squares left or right for free, or one square left or right for a cost of 1. Return the minimum total cost to bring every token onto the same square.
Example 1
- Input:
- positions = [1, 2, 3]
- Output:
- 1
Slide token 3 to square 1 for free, then move the token on square 2 one step for cost 1.
Example 2
- Input:
- positions = [2, 2, 2, 3, 3]
- Output:
- 2
Move both tokens on square 3 onto square 2: cost 1 each.
Constraints
- 1 ≤ positions.length ≤ 100
- 1 ≤ positions[i] ≤ 10^9
Hint
Show the first hint
What can a token reach for free?
Walkthrough
How to approach it
01Clarify before coding
- Can the meeting square be one that no token occupies? Yes, any square.
- Do tokens block each other? No, any number may share a square.
- Are positions bounded? Up to 10^9, so simulating moves is out.
02Brute force
Try every candidate meeting square among the token positions and sum, for each token, 1 if the distance is odd and 0 if even.
Cost: O(n²): fine for n = 100, but it misses why the answer has a closed form, which is what the interviewer is looking for.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.