948. Bag of Tokens

You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

• Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
• Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.

Return the maximum possible score you can achieve after playing any number of tokens.

Example 1:

Input: tokens = [100], power = 50
Output: 0
Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).

Example 2:

Input: tokens = [200,100], power = 150
Output: 1
Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.

Example 3:

Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:

1. Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
2. Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
3. Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
4. Play token2 (300) face-up, reducing power to 0 and increasing score to 2.
   The maximum score achievable is 2.

Constraints:

• 0 <= tokens.length <= 1000
• $0<=tokens[i],power<10^4$

From: LeetCode
Link: 948. Bag of Tokens

Solution:

Ideas:

• Sort tokens in ascending order.

• Use two indices:

  • left for the smallest token (good for playing face-up to gain score cheaply).
  • right for the largest token (good for playing face-down to regain a lot of power).

• While possible:

  • If you have enough power for tokens[left], play it face-up:
    power -= tokens[left]; score++; left++;
    Track the maximum score.
  • Else, if you have at least 1 score and left < right, play tokens[right] face-down:
    power += tokens[right]; score–; right–;
  • Otherwise, you cannot improve anymore, so stop.

Code:

int cmpInt(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);  // equivalent to x - y but safe
}

int bagOfTokensScore(int* tokens, int tokensSize, int power) {
    if (tokensSize == 0) return 0;

    // Sort tokens in ascending order
    qsort(tokens, tokensSize, sizeof(int), cmpInt);

    int left = 0;
    int right = tokensSize - 1;
    int score = 0;
    int maxScore = 0;

    while (left <= right) {
        if (power >= tokens[left]) {
            // Play smallest token face-up
            power -= tokens[left++];
            score++;
            if (score > maxScore) {
                maxScore = score;
            }
        } else if (score > 0 && left < right) {
            // Not enough power: trade score for power using largest token
            power += tokens[right--];
            score--;
        } else {
            // Can't do anything useful anymore
            break;
        }
    }

    return maxScore;
}