Bag Of Tokens Problem


Description

LeetCode Problem 948.

You have an initial power of power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the i^th token (0-indexed).

Your goal is to maximize your total score by potentially playing each token in one of two ways:

  • If your current power is at least tokens[i], you may play the i^th token face up, losing tokens[i] power and gaining 1 score.
  • If your current score is at least 1, you may play the i^th token face down, gaining tokens[i] power and losing 1 score.

Each token may be played at most once and in any order. You do not have to play all the tokens.

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

Example 1:

1
2
3
Input: tokens = [100], power = 50
Output: 0
Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.

Example 2:

1
2
3
4
Input: tokens = [100,200], power = 150
Output: 1
Explanation: Play the 0^th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1^st token since you cannot play it face up to add to your score.

Example 3:

1
2
3
4
5
6
7
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 the 0^th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3^rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1^st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2^nd token (300) face up, your power becomes 0 and score becomes 2.

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int bagOfTokensScore(vector<int>& t, int pw) {
        int pt = 0, max_pt = 0, i = 0, j = t.size() - 1;
        sort(begin(t), end(t));
        while (i <= j && pt >= 0) {
            if (t[i] <= pw) {
                pw -= t[i++]; 
                max_pt = max(max_pt, ++pt);
            }
            else {
                pw += t[j--];
                --pt;
            }
        }
        return max_pt;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...