1140EasyArray

The Badge Filling Over a Quarter of the Roster

Tracked in this browser only

Trains the technique from

LeetCode 1287Element Appearing More Than 25% In Sorted Array

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.

A roster roster of badge numbers is sorted in non-decreasing order. Exactly one badge number takes up more than a quarter of the entries.

Return that badge number.

Examples

Example 1

Input: roster = [1, 2, 2, 3, 3, 3, 3, 4]
Output: 3

Eight entries mean a badge has to appear more than twice. Only 3 does, with four entries, while the two 2 entries are exactly a quarter and so fall short.

Example 2

Input: roster = [5, 5, 5, 5]
Output: 5

Every entry carries the same badge, so it fills the whole roster.

Example 3

Input: roster = [1, 2, 3, 4, 4, 4]
Output: 4

Six entries mean a badge needs at least two. Only 4 repeats at all, three times over.

Constraints

1 <= roster.length <= 10^4
0 <= roster[i] <= 10^5
roster is sorted in non-decreasing order
exactly one badge number takes up more than a quarter of the roster

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 find_special_integer(roster: list[int]) -> int:

Java

public int findSpecialInteger(int[] roster)

The intended approach

Time O(log n) for the searches.Space O(1).

Because the roster is sorted, every badge number sits in one unbroken run, and the one we want has a run longer than a quarter of the roster. A run that long cannot slip between the marks a quarter, a half and three quarters of the way along, since consecutive marks sit exactly a quarter apart. So the answer is whichever badge sits at one of those three marks. Testing a candidate needs its run measured. Find where its run begins by searching for the first entry holding it, then look a quarter of the roster further along: if the badge is still there, the run holds more than a quarter of the entries. Looking exactly a quarter ahead rather than one short is what makes the test strict, so a badge filling exactly a quarter is turned away. Three candidates and one search each is all it takes, so the roster is never walked end to end.

Pythonentry point: find_special_integer

def find_special_integer(roster):
    from bisect import bisect_left
    n = len(roster)
    quarter = n // 4
    for spot in (quarter, n // 2, 3 * n // 4):
        value = roster[spot]
        start = bisect_left(roster, value)
        if start + quarter < n and roster[start + quarter] == value:
            return value
    return roster[0]

The obvious version

Take each entry in turn and sweep the whole roster counting how many share its badge, reporting the first badge whose count times four beats the roster length. Costs the roster length squared.

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_find_special_integer(roster):
    n = len(roster)
    for value in roster:
        count = 0
        for other in roster:
            if other == value:
                count += 1
        if count * 4 > n:
            return value
    return roster[0]

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 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