Bag of Tokens Score

Maximize your score with a bag of tokens and limited power.

greedy two-pointers sorting

You start with an initial power `P` and a score of `0`. You are given a list of token values `tokens` (each token has a face-up value). You may perform any number of the following operations in any order, but each token can be used at most once:

- **Face-up (buy token):** If your current score is at least `1`, you may pay `1` score and gain `tokens[i]` power. This decreases your score by 1 and increases your power by `tokens[i]`.
- **Face-down (sell token):** If your current power is at least `tokens[i]`, you may pay `tokens[i]` power and gain `1` score. This decreases your power by `tokens[i]` and increases your score by 1.

You may use any token at most once (either face-up or face-down, not both). You may stop at any time. Return the **maximum possible score** you can achieve.

Implement the function:

```python
def bag_of_tokens_score(tokens: list[int], power: int) -> int:
```

**Note:** Tokens can be used in any order. It is not required to use all tokens.

Constraints

- `0 <= len(tokens) <= 1000`
- `0 <= tokens[i] <= 10000`
- `0 <= power <= 10000`
- The solution should run in O(n log n) time.

Example

```python
>>> bag_of_tokens_score([100], 50)
0
>>> bag_of_tokens_score([100, 200], 150)
1
>>> bag_of_tokens_score([100, 200, 300, 400], 200)
2
>>> bag_of_tokens_score([81, 91, 31], 73)
1
```

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about sorting the tokens and using two pointers: buy the cheapest token for power, sell the most expensive token for score.

When you cannot buy any more token, consider selling the largest remaining token to gain a score, then try to buy again.

The greedy choice is to always buy the smallest available token when possible and sell the largest when you need more power.

Keep track of the maximum score seen during the process.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.