##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1287.html

# 1287. Element Appearing More Than 25% In Sorted Array (Easy)

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6


Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

Related Topics:
Array

## Solution 1.

• class Solution {
public int findSpecialInteger(int[] arr) {
int length = arr.length;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < length; i++) {
int num = arr[i];
int count = map.getOrDefault(num, 0);
count++;
if (count * 4 > length)
return num;
map.put(num, count);
}
return 0;
}
}

############

class Solution {
public int findSpecialInteger(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; ++i) {
if (arr[i] == arr[i + (n >> 2)]) {
return arr[i];
}
}
return 0;
}
}

• // OJ: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int findSpecialInteger(vector<int>& A) {
int start = 0, N = A.size();
for (int i = 1; i < N; ) {
while (i < N && A[i] == A[start]) ++i;
if (i - start > N / 4) return A[start];
start = i;
}
return A[0];
}
};

• class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
for i, val in enumerate(arr):
if val == arr[i + (n >> 2)]:
return val
return 0

############

# 1287. Element Appearing More Than 25% In Sorted Array
# https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
m = len(arr) // 4

for i in range(n-m+1):
if arr[i] == arr[i+m]:
return arr[i]

• func findSpecialInteger(arr []int) int {
n := len(arr)
for i, val := range arr {
if val == arr[i+(n>>2)] {
return val
}
}
return 0
}

• /**
* @param {number[]} arr
* @return {number}
*/
var findSpecialInteger = function (arr) {
const n = arr.length;
for (let i = 0; i < n; ++i) {
if (arr[i] == arr[i + (n >> 2)]) {
return arr[i];
}
}
return 0;
};


• class Solution {
/**
* @param Integer[] $arr * @return Integer */ function findSpecialInteger($arr) {
$len = count($arr);
for ($i = 0;$i < $len;$i++) {
if ($arr[$i] == $arr[$i + ($len >> 2)]) return$arr[\$i];
}
return -1;
}
}