# Leetcode Daily | 12–09–22 | Bag Of Tokens

Hello everyone,

So from today onwards I have decided to post this blog for the Leetcode daily challenge with its explanation from brute force to optimized one. Since many people face problems while understanding the code, I decided to give a proper explanation for every statement in the code.

Here is the question that we will be looking at today.

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

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

, and a bag of `tokens`

where `tokens[i]`

is the value of the `ith`

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 the`ith`

token face up, losing`tokens[i]`

**power**and gaining`1`

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

, you may play the`ith`

token face down, gaining`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*.

**Constraints:**

`0 <= tokens.length <= 1000`

`0 <= tokens[i], power < 104`

You can find the link to the question here, https://leetcode.com/problems/bag-of-tokens/

**Approach**

For the first approach, we will use two pointers and greedy method. This can only be applied to the array if it is sorted in acending order.

We will place on pointer at the staring and another one at the end. After that, we will teaversing the array till the starting pointer becomes equal to the ending pointer. While traversing, we will keep a track of elements.

If the element is greater than the power, we will look the score and gain the power. Else, if the element is less than the power, we will gain a score and loose the power.

Here is the algorithm that we will be using in this code-

- sort the token in increasing order
- create two pointer i, j, where
`i = 0, j = n`

; initially `0 <= x <= i`

represent the tokens face up i.e, [Score ⬆, Power ⬇]`j <= x <= n`

represent the tokens face down i.e, [Score ⬇, Power⬆]- if we have sufficient power to face up ith token, power — token[i], i++.
- else if we have some score
`[i - (n - j)]`

face down jth token,`j--, power + token[j]`

.`i - (n - j) represents the score since (face up - face down) = score, face up = i and face down = n - j`

**Note**:`we also need to check if we face down j we should have some unplayed token to face up. That's why we are checking j > i + 1`

- if we have no move to make break the loop.

**C++ Code**

**Java Code**

**Python Code**

The time complexity of the above code is **O(nlogn) **and the space complexity is** O(1).**