Bag of Tokens

Medium

Apple

2 views

Topics:

ArraysGreedy AlgorithmsTwo PointersStrings

You are given 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 token_i.

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 token_i, losing tokens[i] power and gaining 1 score.
Face-down: If your current score is at least 1, you may play token_i, gaining tokens[i] power and losing 1 score.

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

Example 1:

tokens = [100], power = 50

Output: 0

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:

tokens = [200,100], power = 150

Output: 1

Play token₁ (100) face-up, reducing your power to 50 and increasing your score to 1.

Example 3:

tokens = [100,200,300,400], power = 200

Output: 2

Play the tokens in this order to get a score of 2:

Play token₀ (100) face-up, reducing power to 100 and increasing score to 1.
Play token₃ (400) face-down, increasing power to 500 and reducing score to 0.
Play token₁ (200) face-up, reducing power to 300 and increasing score to 1.
Play token₂ (300) face-up, reducing power to 0 and increasing score to 2.

Bag of Tokens

Medium

Apple

2 views

Topics:

ArraysGreedy AlgorithmsTwo PointersStrings

You are given 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 token_i.

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 token_i, losing tokens[i] power and gaining 1 score.
Face-down: If your current score is at least 1, you may play token_i, gaining tokens[i] power and losing 1 score.

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

Example 1:

tokens = [100], power = 50

Output: 0

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:

tokens = [200,100], power = 150

Output: 1

Play token₁ (100) face-up, reducing your power to 50 and increasing your score to 1.

Example 3:

tokens = [100,200,300,400], power = 200

Output: 2

Play the tokens in this order to get a score of 2:

Play token₀ (100) face-up, reducing power to 100 and increasing score to 1.
Play token₃ (400) face-down, increasing power to 500 and reducing score to 0.
Play token₁ (200) face-up, reducing power to 300 and increasing score to 1.
Play token₂ (300) face-up, reducing power to 0 and increasing score to 2.

Solution

Brute Force Solution

A brute force approach would involve trying all possible combinations of playing tokens face-up or face-down and keeping track of the maximum score achieved. This approach is not efficient.

Complexity Analysis:

Time Complexity: O(2ⁿ), where n is the number of tokens, since each token can either be played face-up or face-down.
Space Complexity: O(n) due to the recursion depth in the worst case.

Optimal Solution: Greedy Algorithm

The optimal solution uses a greedy approach. We sort the tokens and use two pointers, one at the beginning and one at the end of the sorted array. We try to play the smallest token face-up to increase our score, and if we can't, we try to play the largest token face-down to increase our power. This strategy maximizes our score by efficiently utilizing the available power and tokens.

Algorithm:

Sort the tokens in ascending order.
Initialize two pointers, left at 0 and right at tokens.length - 1.
Initialize power and score to their initial values.
While left <= right:
- If power >= tokens[left], play the token face-up: decrease power by tokens[left], increase score by 1, and move left one step to the right.
- Else if score > 0 and left < right, play the token face-down: increase power by tokens[right], decrease score by 1, and move right one step to the left.
- Else, break the loop because no more moves are possible.
Return the maximum score achieved.

Edge Cases:

If the initial power is less than the smallest token and the score is 0, the maximum score is 0.
If the token array is empty, the maximum score is 0.
If all tokens can be played face-up, the maximum score is tokens.length.

Complexity Analysis:

Time Complexity: O(n log n) due to sorting the tokens, where n is the number of tokens. The rest of the algorithm takes O(n) time.
Space Complexity: O(1) as we use constant extra space.

Code Implementation (Java):

import java.util.Arrays;

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int left = 0;
        int right = tokens.length - 1;
        int score = 0;
        int maxScore = 0;

        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = Math.max(maxScore, score);
            } else if (score > 0 && left < right) {
                power += tokens[right];
                score--;
                right--;
            } else {
                break;
            }
        }

        return maxScore;
    }
}

Solution

Brute Force Solution

A brute force approach would involve trying all possible combinations of playing tokens face-up or face-down and keeping track of the maximum score achieved. This approach is not efficient.

Complexity Analysis:

Time Complexity: O(2ⁿ), where n is the number of tokens, since each token can either be played face-up or face-down.
Space Complexity: O(n) due to the recursion depth in the worst case.

Optimal Solution: Greedy Algorithm

Algorithm:

Sort the tokens in ascending order.
Initialize two pointers, left at 0 and right at tokens.length - 1.
Initialize power and score to their initial values.
While left <= right:
- If power >= tokens[left], play the token face-up: decrease power by tokens[left], increase score by 1, and move left one step to the right.
- Else if score > 0 and left < right, play the token face-down: increase power by tokens[right], decrease score by 1, and move right one step to the left.
- Else, break the loop because no more moves are possible.
Return the maximum score achieved.

Edge Cases:

If the initial power is less than the smallest token and the score is 0, the maximum score is 0.
If the token array is empty, the maximum score is 0.
If all tokens can be played face-up, the maximum score is tokens.length.

Complexity Analysis:

Time Complexity: O(n log n) due to sorting the tokens, where n is the number of tokens. The rest of the algorithm takes O(n) time.
Space Complexity: O(1) as we use constant extra space.

Code Implementation (Java):

import java.util.Arrays;

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int left = 0;
        int right = tokens.length - 1;
        int score = 0;
        int maxScore = 0;

        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = Math.max(maxScore, score);
            } else if (score > 0 && left < right) {
                power += tokens[right];
                score--;
                right--;
            } else {
                break;
            }
        }

        return maxScore;
    }
}