Problem

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.

Examples

Example 1

1
2
3
4
5
6


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

Example 2

1
2
3
4
5
6


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

Constraints

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

Solution

Method 1 – Binary Search (or Linear Scan)

Intuition

Since the array is sorted and there is exactly one element that appears more than 25% of the time, it must appear at least at one of the positions: n//4, n//2, or 3n//4. We can check these positions and count the occurrences of the candidate using binary search or a simple scan.

Approach

  1. Let n be the length of arr.
  2. For each candidate at positions n//4, n//2, and 3n//4, check if it appears more than n//4 times by comparing arr[i] and arr[i + n//4].
  3. Return the first such candidate found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

func findSpecialInteger(arr []int) int {
    n := len(arr)
    k := n / 4
    for _, i := range []int{k, 2 * k, 3 * k} {
        if i+k < n && arr[i] == arr[i+k] {
            return arr[i]
        }
    }
    return arr[0]
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length, k = n / 4;
        for (int i : new int[]{k, 2 * k, 3 * k}) {
            if (i + k < n && arr[i] == arr[i + k]) return arr[i];
        }
        return arr[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun findSpecialInteger(arr: IntArray): Int {
        val n = arr.size
        val k = n / 4
        for (i in listOf(k, 2 * k, 3 * k)) {
            if (i + k < n && arr[i] == arr[i + k]) return arr[i]
        }
        return arr[0]
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def findSpecialInteger(self, arr: list[int]) -> int:
        n = len(arr)
        k = n // 4
        for i in [k, 2 * k, 3 * k]:
            if i + k < n and arr[i] == arr[i + k]:
                return arr[i]
        return arr[0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn find_special_integer(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let k = n / 4;
        for &i in &[k, 2 * k, 3 * k] {
            if i + k < n && arr[i] == arr[i + k] {
                return arr[i];
            }
        }
        arr[0]
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    findSpecialInteger(arr: number[]): number {
        const n = arr.length, k = Math.floor(n / 4);
        for (const i of [k, 2 * k, 3 * k]) {
            if (i + k < n && arr[i] === arr[i + k]) return arr[i];
        }
        return arr[0];
    }
}

Complexity

  • ⏰ Time complexity: O(1), since we only check a few positions.
  • 🧺 Space complexity: O(1), no extra space is used.