Element Appearing More Than 25% In Sorted Array
Problem
Given a sorted array of integers, there is exactly one integer that appears more than 25% of the time. Return that integer.
arr = [1, 2, 2, 6, 6, 6, 6, 7, 10]6def find_special_integer(arr):
n = len(arr)
step = n // 4
for i in (0, step, 2 * step, 3 * step):
if arr[i] == arr[i + step]:
return arr[i]
return arr[0]function findSpecialInteger(arr) {
const n = arr.length;
const step = Math.floor(n / 4);
for (const i of [0, step, 2 * step, 3 * step]) {
if (arr[i] === arr[i + step]) return arr[i];
}
return arr[0];
}class Solution {
public int findSpecialInteger(int[] arr) {
int n = arr.length;
int step = n / 4;
int[] candidates = { 0, step, 2 * step, 3 * step };
for (int i : candidates) {
if (arr[i] == arr[i + step]) return arr[i];
}
return arr[0];
}
}int findSpecialInteger(vector<int>& arr) {
int n = (int)arr.size();
int step = n / 4;
for (int i : { 0, step, 2 * step, 3 * step }) {
if (arr[i] == arr[i + step]) return arr[i];
}
return arr[0];
}Explanation
Because the array is sorted, all copies of a value sit in one contiguous block. A value that fills more than 25% of the array spans a run longer than n/4 — and a run that long must cover at least one of a few fixed checkpoints.
The checkpoints are the quarter marks: indices 0, step, 2*step, and 3*step, where step = n // 4. Any block longer than n/4 is guaranteed to contain one of these positions.
For each candidate index i we compare arr[i] with arr[i + step]. If they're equal, the same value spans a window of length step + 1 > n/4, so it must be the special element and we return it.
This checks only a constant number of positions, so it's effectively O(1) (and O(log n) if you replace the linear span check with a binary search for the run's edges).
Example: arr = [1, 2, 2, 6, 6, 6, 6, 7, 10], n = 9, step = 2. At i = 3, arr[3] = 6 equals arr[3 + 2] = arr[5] = 6, so the answer is 6.