How to Solve the Bag of Tokens Challenge in Java
The challenge
You have an initial power of P
, an initial score of ``, and a bag of tokens
where tokens[i]
is the value of the i<sup>th</sup>
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 thei<sup>th</sup>
token face up, losingtokens[i]
power and gaining1
score. - If your current score is at least
1
, you may play thei<sup>th</sup>
token face down, gainingtokens[i]
power and losing1
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:
Example 2:
Example 3:
Constraints:
0 <= tokens.length <= 1000
0 <= tokens[i], P < 10<sup>4</sup>
The solution in Java code
class Solution {
public int bagOfTokensScore(int[] tokens, int P) {
Arrays.sort(tokens);
int played = tokens.length;
int i = 0;
int j = tokens.length - 1;
int score = 0 ;
while(played > 0) {
if(tokens[i] <= P) {
P -= tokens[i++];
score++;
played--;
} else if(tokens[i] > P && score > 0 && played > 1) {
P += tokens[j--];
score--;
played--;
} else break;
}
return score;
}
}