Bag of Tokens

Photo by Shot by Cerqueira @shotbycerqueira on Unsplash

Description

You have an initial power P, an initial score of 0 points, and a bag of tokens.

Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

• If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
• If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.

Return the largest number of points we can have after playing any number of tokens.

Examples

Input: tokens = [100], P = 50
Output: 0
Input: tokens = [100,200], P = 150
Output: 1
Input: tokens = [100,200,300,400], P = 200
Output: 2

1. tokens.length <= 1000
2. 0 <= tokens[i] < 10000
3. 0 <= P < 10000

Analyses

In short, this is a typical greedy problem, we want to get the most points with the least power. To solve the greedy problem, usually, we need to figure out which cases can rule out the others.

The description is a little bit fancy, a token has two usage — either exchanging power for 1 point or the other way around. To be clear, a token can be used at most once and we need to get as many points as possible. Intuitively, we would like to use 1 point to exchange for the largest power, while sacrifice the least power to exchange for 1 point.

Generally, the problem is an exchange problem, in which we trade our power for points and the other round as well. However, the trade is not fair — one point can worth the max power among the tokens, on the other hand, we are able to just spend the min power among the token to obtain one point. Our goal is to get the max points as we can, which actually, is equivalent to gaining max power since the more power we have, the more points we can exchange.

For example, given these tokens [100,200,300,400] and 500 power and 1 point, if we want to reach max power, which token will you use? Obvious to make the most of the point, we would choose 400, thus I can own 900 power in the end. For another, if owning max points is our goal, which token shall we consider first? Well, I would choose 100 since I can have 2 points with 400 power left, which has the most potential for the next trade (In fact, if we convert the points to power, we will have 900 power as well, as is the max power we can hold).

As we can see, there are two basic rules to follow:

1. Exchange points for the largest power (point => power)
2. Exchange the least power for points (power => point)

Naturally, sorting is needed to arrange the power (here in ascending order) so that the largest and least power can be fetched easily, as appear at both ends of the array. We sacrifice the power as least as possible for points, meaning to travel from left to right. Meanwhile, we use points to exchange power as large as possible, indicating the direction is from right to left so that we have more potential to exchange for more points.

As in example [100,200,300,400] with 200 power, i=0 and j=3 are used to mark the left and right pointers (since medium doesn’t support strikethrough, bold is used to indicate used token)

1. Since we don’t have any point, power is used to exchange for points, thus we apply thepower => point rule, and we have [100, 200, 300, 400], 1 point, 100 power
2. 100 power is less than the least power among the available tokens, we apply point => power to get more potential for points, ending with [100, 200, 300, 400], 0 points, 500 power
3. apply power => point to be [100, 200, 300, 400], 1 point, 300 power
4. apply power => point to be [100, 200, 300, 400], 2 points, 0 power

Finally, we get two points. Since each token can be used at most once, when the two pointers meet, the loop ends. Also, if we run out of power and points at the same time, the final result is reached since there is no way to continue.

Conclusion

The greedy problem usually can be derived from the dynamic programming problem, there exists a common pattern — some situation will rule out other ones so we can prune some unnecessary branches.