Spend Tokens for Points
MediumGreedy
Problem
You start with power energy and 0 points. Each token in tokens can be used at most once, in one of two ways:
Spend: if your energy is at least tokens[i], lose that much energy and gain 1 point. Cash in: if you have at least 1 point, lose 1 point and gain tokens[i] energy.
Tokens may be used in any order, and you may leave some unused. Return the largest number of points you can hold at any moment.
Example 1
- Input:
- tokens = [30, 90, 60, 10], power = 40
- Output:
- 2
Spend 10 and 30 (2 points, 0 energy), cash in 90 (1 point, 90 energy), spend 60 (2 points).
Example 2
- Input:
- tokens = [100, 200], power = 150
- Output:
- 1
Example 3
- Input:
- tokens = [100], power = 50
- Output:
- 0
Constraints
- 0 ≤ tokens.length ≤ 1000
- 0 ≤ tokens[i], power < 10^4
Hint
Show the first hint
Each point costs one token's value whichever token you spend. Which tokens should you spend?
Walkthrough
How to approach it
01Clarify before coding
- Is the answer the final score or the best score seen? The best score at any moment, so a final cash-in that lowers the score does not hurt.
- Must every token be used? No.
- Can tokens be 0? Yes; a 0 token gives a free point.
02Brute force
Search over all orders and choices (spend, cash in, skip) for every token.
Cost: O(3^n · n!) naively, or exponential memoisation over used-sets: hopeless for 1000 tokens.
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.