0703EasyMathGreedy

Badges at the Token Counter

Tracked in this browser only

Trains the technique from

LeetCode 2591Distribute Money to Maximum Children

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An arcade attendant has tokens tokens to hand out across players players waiting at the counter. The house rules are:

every token must be handed out;
every player must leave with at least one token;
no player may leave with exactly four tokens, a count the arcade considers unlucky.

A player who leaves with exactly eight tokens is also given a free badge.

Return the largest number of badges the attendant can award. If no handout satisfies all three rules, return -1.

Examples

Example 1

Input: tokens = 24, players = 3
Output: 3

Handing eight tokens to each player uses all 24, gives everyone at least one and leaves nobody on exactly four, so all three players collect a badge.

Example 2

Input: tokens = 10, players = 2
Output: 1

Handing out eight and two tokens uses all ten, gives both players at least one and leaves neither on exactly four. One player holds eight, so one badge is awarded.

Example 3

Input: tokens = 12, players = 2
Output: 0

Handing out five and seven tokens uses all twelve, gives both players at least one and leaves neither on exactly four. Neither player holds eight, so no badge is awarded.

Example 4

Input: tokens = 1, players = 2
Output: -1

One token cannot give two players at least one each, so no handout satisfies the rules.

Constraints

1 <= tokens <= 200
2 <= players <= 30

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def most_badges(tokens: int, players: int) -> int:

Java

public int mostBadges(int tokens, int players)

The intended approach

Time O(1): a handful of integer operations, independent of the token and player counts.Space O(1).

Fewer tokens than players makes the one-each rule impossible, so that case returns -1. Otherwise give everybody one token and look at the surplus: each badge costs seven more tokens, so the badge count is the surplus divided by seven, capped at the number of players. Two situations then need a repair. If every player was lifted to eight and tokens are still unspent, someone has to absorb them and loses their badge. If exactly one player was left out and the surplus left over is three, that player would be holding four tokens, so one badge has to be given up to free the surplus.

Pythonentry point: most_badges

def most_badges(tokens, players):
    # O(1): hand every player one token first, then spend the surplus seven at a
    # time to lift a player to eight, and repair the two ways the last player can
    # be left holding an amount the rules forbid.
    if tokens < players:
        return -1
    surplus = tokens - players
    badges = surplus // 7
    if badges > players:
        badges = players
    surplus -= badges * 7
    remaining = players - badges
    if remaining == 0:
        if surplus > 0:
            badges -= 1
    elif remaining == 1 and surplus == 3:
        badges -= 1
    return badges

The obvious version

A table over the number of players served and the number of tokens used, filled by trying every legal amount for the next player and keeping the largest badge count reachable. Explores every handout the rules allow, at a cost proportional to the players times the square of the token count.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_most_badges(tokens, players):
    NEG = -1000
    prev = [NEG] * (tokens + 1)
    prev[0] = 0
    for _ in range(players):
        cur = [NEG] * (tokens + 1)
        for total in range(1, tokens + 1):
            best = NEG
            for give in range(1, total + 1):
                if give == 4:
                    continue
                earlier = prev[total - give]
                if earlier == NEG:
                    continue
                cand = earlier + (1 if give == 8 else 0)
                if cand > best:
                    best = cand
            cur[total] = best
        prev = cur
    return prev[tokens] if prev[tokens] != NEG else -1

How this problem was checked

Reference solution executed against 22 test cases — 22 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in