Skip to content

1287. Element Appearing More Than 25% In Sorted Array

SourceBiweekly Contest 15 Q1DifficultyEasyRating1179

Description

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

Example 2:

Input: arr = [1,1]
Output: 1

 

Constraints:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 105

Solutions

Solution 1: Traversal

Thinking

In a sorted array some value occurs more than \(25\%\), i.e. spans at least \(\lfloor n/4 \rfloor\). If \(\textit{arr}[i]=\textit{arr}[i+\lfloor n/4 \rfloor]\), that value already covers enough length. The first hit from the left is the answer; sorted order turns counting into an index comparison.

We traverse the array \(\textit{arr}\) from the beginning. For each element \(\textit{arr}[i]\), we check if \(\textit{arr}[i]\) is equal to \(\textit{arr}[i + \left\lfloor \frac{n}{4} \right\rfloor]\), where \(n\) is the length of the array. If they are equal, then \(\textit{arr}[i]\) is the element we are looking for, and we return it directly.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{arr}\).

1
2
3
4
5
6
class Solution:
    def findSpecialInteger(self, arr: list[int]) -> int:
        n = len(arr)
        for i, x in enumerate(arr):
            if x == arr[(i + (n >> 2))]:
                return x

1
2
3
4
5
6
7
8
9
class Solution {
    public int findSpecialInteger(int[] arr) {
        for (int i = 0;; ++i) {
            if (arr[i] == (arr[i + (arr.length >> 2)])) {
                return arr[i];
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        for (int i = 0;; ++i) {
            if (arr[i] == (arr[i + (arr.size() >> 2)])) {
                return arr[i];
            }
        }
    }
};

1
2
3
4
5
6
7
func findSpecialInteger(arr []int) int {
    for i := 0; ; i++ {
        if arr[i] == arr[i+len(arr)/4] {
            return arr[i]
        }
    }
}

1
2
3
4
5
6
7
8
function findSpecialInteger(arr: number[]): number {
    const n = arr.length;
    for (let i = 0; ; ++i) {
        if (arr[i] === arr[i + (n >> 2)]) {
            return arr[i];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @param {number[]} arr
 * @return {number}
 */
var findSpecialInteger = function (arr) {
    const n = arr.length;
    for (let i = 0; ; ++i) {
        if (arr[i] === arr[i + (n >> 2)]) {
            return arr[i];
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function findSpecialInteger($arr) {
        $n = count($arr);
        for ($i = 0; ; ++$i) {
            if ($arr[$i] == $arr[$i + ($n >> 2)]) {
                return $arr[$i];
            }
        }
    }
}

Comments