187. Power Token Play
An arcade machine shows a row of tokens, where tokens[i] is the value of token i. You start with power energy points and a score of 0. Each token may be played at most once, in any order you like, in one of two ways.
Played face up, a token costs its value in energy and gives 1 point; it needs energy >= value. Played face down, a token gives you its value in energy and costs 1 point; it needs a score of at least 1. You may also leave tokens unplayed. Return the largest score you can have at any moment while playing. If there are no tokens, the answer is 0.
Example 1
- Input:
- tokens = [100,200,300,400], power = 200
- Output:
- 2
- Explanation:
Play 100 face up (energy 100, score 1), flip 400 face down (energy 500, score 0), then play 200 and 300 face up for a score of 2. No sequence reaches 3.
Example 2
- Input:
- tokens = [50], power = 40
- Output:
- 0
- Explanation:
The only token costs 50 but you have 40 energy and no points to flip anything, so the score stays 0.
Example 3
- Input:
- tokens = [10,20], power = 25
- Output:
- 1
- Explanation:
Play 10 face up and keep the rest of your energy: score 1. Playing 20 afterwards needs 20 but only 15 remain, and flipping 20 face down costs your point, so 1 is the best.
Constraints
0 ≤ tokens.length ≤ 105
0 ≤ tokens[i] ≤ 104
0 ≤ power ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(1) extra