EasyArraysAI interview only
Element Appearing More Than 25 Percent In Sorted Array
Asked atgoogleamazonmetabloomberg
01 · Problem
You are given an integer array arr sorted in non-decreasing order. Exactly one value occurs in arr strictly more than 25% of the time, that is, more than arr.length / 4 times.
Return that value. The input is guaranteed to contain exactly one such value.
02 · Examples
Example 01
Input
arr = [3,5,5,5,5,8,9,9]
Output
5
The array has 8 elements, so the target must appear more than 2 times. The value 5 appears 4 times; 9 appears exactly 2 times, which is not enough.
Example 02
Input
arr = [4]
Output
4
A single element makes up 100% of the array.
Example 03
Input
arr = [1,1,2,3,4]
Output
1
The value 1 appears 2 times out of 5, which is more than 5 / 4 = 1.25.
03 · Constraints
- 011 <= arr.length <= 104
- 020 <= arr[i] <= 105
- 03arr is sorted in non-decreasing order
- 04Exactly one value appears more than arr.length / 4 times
04 · Optimal complexity
- Time
- O(log n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.