Header Ads Widget

Develop Your Creative Skill with
Free Design Tutorials

Our blog helps to Provide Latest Tips and Tricks tutorials about Blogging
Business, SEO Tips, much more. this Blog and stay tuned to this
blog for further updates.

Bag of Tokens leetcode

 Problem- Bag of Tokens

Leetcode Problem number 948

Bag of Tokens is an important question based on sorting and two-pointer concepts. This is the most commonly asked question in coding interviews.


 Let us understand the Bag of Tokens Problem

We have given a Power 'P' and a bag of tokens in the form of an Array. we have to maximize our score by utilizing these powers.

Rules for Bag of Tokens Problem

  • If Your current Power is greater than Token[i], you can increase your score by losing power equivalent to Power-Token[i].
  • If Your score is greater than '1', you can either play face up or face down.

1. What is Face Up in Bag of Tokens Problem

Face Up means increase the Score by 1 and decrease power by Token[i].

2. What is Face Down in Bag of Tokens Problem

Face Down means decrease score by 1 and increase power by Token[i], where i is an index of Token array.

Bag of Tokens Problem


Lebel: Medium

Let us see some examples based on Input-Output of Bag of Tokens Problem
Example 1:

Input = [100,900,300,400,1200]
Power = 200
Output : 2 


Example 2:

Input = [100,120]
Power = 10
Output : 0 


Steps to Solve Bag of Tokens Problem

  • Sort the Given array in Ascending Order
  • Initialize to Pointer variable one from initial and other from last of the array.
  • Iterate Through the array and perform your logic.

    Solution for Bag of Tokens Problem


Solution in Java

class Solution {
    public int bagOfTokensScore(int[] tokensint power) {
        Arrays.sort(tokens);
        int i=0;
        int j=tokens.length-1;
        int points=0;
        int res=0;
        while(i<=j)
        {
            if(power>=tokens[i])
            {
                power-=tokens[i++];
                res=Math.max(res,++points);
            }
            else if(points>0)
            {
               points--;
                power+=tokens[j--];
            }
            else
            {
                break;
            }
            
            
            
        }
        return res;
    }
}



Solution of Bag of Tokens Problem in C++


class Solution {
public:
    int bagOfTokensScore(vector<int>& tokensint power) {
        sort(tokens.begin(),tokens.end());
        int i=0,j,score=0,res=0;
        j=tokens.size()-1;
        while(i<=j)
        {
            if(power>=tokens[i])
            {
                score++;
                power-=tokens[i];
                i++;
            }
            else if(score>0)
            {
                score--;
                power+=tokens[j];
                j--;
            }
            else
            {
                break;
            }
            res=max(res,score);
        }
        return res;
    }
};



Solution of Bag of Tokens Problem In Python

class Solution:
    def bagOfTokensScore(selftokens: List[int], Pint) -> int:
        tokens.sort()
        L, H = 0len(tokens)-1
        score, res = 00
        while L <= H:
            if tokens[L] <= P:
                P-=tokens[L]
                score+=1
                res = max(score, res)
                L+=1
            elif score >= 1:
                P+=tokens[H]
                score-=1
                H-=1
            else:
                break
        return res



Practice This question on Leetcode - Bag of Tokens Problem
There can be another approach also to solve this problem such as the greedy approach or by using Queue. I have solved using Two pointer algorithm so that you can understand the basic approach of this problem.