## 948. Bag of Tokens

You have an initial **power** of `P`

, an initial **score** of `0`

, and a bag of `tokens`

where `tokens[i]`

is the value of the `i`

token (0-indexed).^{th}

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`

token face up, losing^{th}`tokens[i]`

**power**and gaining`1`

**score**. - If your current
**score**is at least`1`

, you may play the`i`

token face down, gaining^{th}`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:**

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

**Example 2:**

Input:tokens = [100,200], P = 150Output:1Explanation: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:**

Input:tokens = [100,200,300,400], P = 200Output:2Explanation: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], P < 10`

^{4}

## Rust Solution

```
struct Solution;
impl Solution {
fn bag_of_tokens_score(mut tokens: Vec<i32>, mut p: i32) -> i32 {
let n = tokens.len();
if n == 0 {
return 0;
}
tokens.sort_unstable();
let mut l = 0;
let mut r = n - 1;
let mut point = 0;
let mut res = 0;
while l <= r {
if tokens[l] <= p {
p -= tokens[l];
point += 1;
res = res.max(point);
l += 1;
} else {
if point > 0 {
p += tokens[r];
point -= 1;
r -= 1;
} else {
break;
}
}
}
res
}
}
#[test]
fn test() {
let tokens = vec![100];
let p = 50;
let res = 0;
assert_eq!(Solution::bag_of_tokens_score(tokens, p), res);
let tokens = vec![100, 200];
let p = 150;
let res = 1;
assert_eq!(Solution::bag_of_tokens_score(tokens, p), res);
let tokens = vec![100, 200, 300, 400];
let p = 200;
let res = 2;
assert_eq!(Solution::bag_of_tokens_score(tokens, p), res);
}
```

Having problems with this solution? Click here to submit an issue on github.