Skip to content

948. Bag of Tokens 👍

  • Time:
  • Space:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int bagOfTokensScore(vector<int>& tokens, int power) {
    int ans = 0;
    int score = 0;
    int i = 0;                  // index of smallest token
    int j = tokens.size() - 1;  // index of largest token

    sort(begin(tokens), end(tokens));

    while (i <= j && (power >= tokens[i] || score)) {
      while (i <= j && power >= tokens[i]) {
        // play the smallest face up
        power -= tokens[i++];
        ++score;
      }
      ans = max(ans, score);
      if (i <= j && score) {
        // play the largest face down
        power += tokens[j--];
        --score;
      }
    }

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int bagOfTokensScore(int[] tokens, int power) {
    int ans = 0;
    int score = 0;
    int i = 0;                 // index of smallest token
    int j = tokens.length - 1; // index of largest token

    Arrays.sort(tokens);

    while (i <= j && (power >= tokens[i] || score > 0)) {
      while (i <= j && power >= tokens[i]) {
        // play the smallest face up
        power -= tokens[i++];
        ++score;
      }
      ans = Math.max(ans, score);
      if (i <= j && score > 0) {
        // play the largest face down
        power += tokens[j--];
        --score;
      }
    }

    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
    ans = 0
    score = 0
    q = deque(sorted(tokens))

    while q and (power >= q[0] or score):
      while q and power >= q[0]:
        # play the smallest face up
        power -= q.popleft()
        score += 1
      ans = max(ans, score)
      if q and score:
        # play the largest face down
        power += q.pop()
        score -= 1

    return ans