Show problems as
Classic problem #1287EasyArray

Element Appearing More Than 25% In Sorted Array

Real-world version: The Badge Filling Over a Quarter of the Roster
Tracked in this browser only
Read Element Appearing More Than 25% In Sorted Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_special_integer(roster: list[int]) -> int:
Java
public int findSpecialInteger(int[] roster)

More on the same topics