LeetCode Entry

948. Bag of Tokens

04.03.2024 medium 2024 kotlin rust

Max score converting power to token[i] and token[i] to score.

948. Bag of Tokens medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/528

Problem TLDR

Max score converting power to token[i] and token[i] to score. #medium

Intuition

Let’s observe some examples by our bare hands:

    // 100 200 300 400     p 200  s 0
    // -                     100    1
    //             +         500    0
    //     -                 300    1
    //         -             0      2
    // 200 400 400 400     p 200  s 0
    // -                       0    1
    //             +         400    0
    //     -

As we can see, the greedy approach can possibly be the optimal one after sorting the array.

Approach

  • careful with empty arrays in Rust: len() - 1 will crash

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\)

Code


  fun bagOfTokensScore(tokens: IntArray, power: Int): Int {
    tokens.sort()
    var i = 0; var j = tokens.lastIndex
    var p = power; var s = 0; var m = 0
    while (i <= j)
      if (p >= tokens[i]) { p -= tokens[i++]; m = max(m, ++s) }
      else if (s-- > 0) p += tokens[j--] else break
    return m
  }



  pub fn bag_of_tokens_score(mut tokens: Vec<i32>, mut power: i32) -> i32 {
    tokens.sort_unstable(); if tokens.is_empty() { return 0 }
    let (mut i, mut j, mut s, mut m) = (0, tokens.len() - 1, 0, 0);
    while i <= j {
      if power >= tokens[i] {
        s += 1; power -= tokens[i]; i += 1; m = m.max(s)
      } else if s > 0 {
        s -= 1; power += tokens[j]; j -= 1;
      } else { break }
    }; m
  }