Practice/Oracle/Leetcode 948. Bag of Tokens

Leetcode 948. Bag of Tokens

CodingMust

Problem

You are given an array of integers called tokens where each token has a point value, and you start with an initial amount of power. You can play tokens in two different ways:

1. Face-up: If your current power is at least equal to a token's value, you can play that token face-up. This costs you power equal to the token's value and grants you 1 point of score.
2. Face-down: If your current score is at least 1, you can play any token face-down. This costs you 1 point of score and grants you power equal to the token's value.

Each token can only be played once. Your goal is to maximize your final score after making any number of moves (including zero moves).

Requirements

1. Return the maximum possible score you can achieve
2. Each token can be used at most once
3. You may play tokens in any order you choose
4. You can switch between face-up and face-down plays as needed
5. If you cannot make any beneficial moves, you should stop

Constraints

• 0 ≤ tokens.length ≤ 1000
• 0 ≤ tokens[i] ≤ 10000
• 0 ≤ power ≤ 10000
• Time complexity should be O(n log n) or better
• Space complexity should be O(1) excluding the space needed for sorting

Examples

Example 1:

Input: tokens = [100], power = 50 Output: 0 Explanation: We don't have enough power to play the token face-up, and we have no score to play it face-down. The maximum score is 0.

Example 2:

` Input: tokens = [100, 200, 300, 400], power = 200 Output: 2 Explanation:

• Play token with value 100 face-up: power becomes 100, score becomes 1
• Play token with value 200 face-up: power becomes 0, score becomes 2
• We cannot play any more tokens face-up (insufficient power)
• Playing a token face-down would reduce our score, which doesn't help
• Maximum score achieved is 2 `

Example 3:

` Input: tokens = [100, 200], power = 150 Output: 1 Explanation:

• Play token with value 100 face-up: power becomes 50, score becomes 1
• We cannot play the token with value 200 (need 200 power but only have 50)
• Maximum score is 1 `