Problem Explanation

Given an integer array sorted in non-decreasing order, there is one number that occurs more than 25% of the time. Our task is to find and return that integer.

For example, consider the following array :

Input Array : [1,2,2,6,6,6,6,7,10]

The output for this input should be 6, as 6 appears 4 times which is more than 25% of the size of the array, which is 9 in this case.

Approach

The approach is fairly simple:

1. Calculate the quarter of the size of the array and store it in variable quarter.
2. Iterate through the array.
3. Check if the current element and the element at the current index plus quarter of the size of the array are same. If they are same, return the current element.
4. If no such element is found, then throw an exception.

Steps

Now, let's walk through the steps of the approach using the example given above.

Input Array: [1,2,2,6,6,6,6,7,10]

1. Calculate the quarter of the size of the array, which is integer value of 9/4, which equals 2.
2. Start iterating through the array from the 0th index.
3. Check if the current element and the element at the current index plus quarter of the size of the array are same. If they are same, return the current element. In this case, the element at the 0th index is not equal to the element at (0+2)=2th index. So, move on to the next.
4. Repeat step 3 until you find such an element or reach the end of the array. In this case, the element at the 2nd index is equal to the element at (2+2)=4th index. Hence, return 6.

Implementation

Python

1
2python
3class Solution:
4 def findSpecialInteger(self, arr):
5    n = len(arr)
6    quarter = n / 4
7    for i in range(0, n - quarter):
8      if arr[i] == arr[i + quarter]: return arr[i]
9    return -1

Java

1
2java
3class Solution {
4 public int findSpecialInteger(int[] arr) {
5    int n = arr.length;
6    int quarter = n / 4;
7    for (int i = 0; i < n - quarter; i++){
8      if (arr[i] == arr[i + quarter]) return arr[i];
9    }
10    return -1;
11  }
12}

JavaScript

1
2javascript
3class Solution {
4 findSpecialInteger(arr) {
5    const n = arr.length;
6    const quarter = Math.floor(n / 4);
7    for (let i = 0; i < n - quarter; i++){
8      if (arr[i] === arr[i + quarter]) return arr[i];
9    }
10    return -1;
11 }
12}

C++

1
2cpp
3class Solution {
4public:
5  int findSpecialInteger(vector<int>& arr) {
6    const int n = arr.size();
7    const int quarter = n / 4;
8    for (int i = 0; i < n - quarter; ++i){
9      if(arr[i] == arr[i + quarter]) return arr[i];
10    }
11    throw;
12  }
13};

C#

1
2csharp
3public class Solution {
4  public int findSpecialInteger(int[] arr) {
5    int n = arr.Length;
6    int quarter = n / 4;
7    for (int i = 0; i < n - quarter; i++) {
8      if(arr[i] == arr[i + quarter]) return arr[i];
9    }
10    return -1;
11  }
12}

Final Note

In case the input array is properly formed and according to the constraint, there will always be an integer that is repeated more than 25% of the time, so we don't need to handle the case when no such integer exists. However, in the C++ solution, a "throw" is used to end the execution in case no integer found that satisfies the criteria, while for Python, Java, JavaScript, and C#, -1 is returned.This problem can be solved in O(n) complexity by the method described above. An alternate method could be to use a hash map to count the frequency of all the numbers in the array and then find the number than occurs more than n/4 times. This method would also have O(n) complexity but would require extra space for the hash map. Note that the original method only works because the input array is sorted. If the array was not sorted, the elements in 'arr[i]' and 'arr[i+quarter]' could be different even if one of them occurs more than n/4 times, hence the method with hash map would need to be applied.

Alternate Python solution with a hash map

1
2python
3from collections import defaultdict
4class Solution:
5  def findSpecialInteger(self, arr):
6    counts = defaultdict(int)
7    n = len(arr)
8    for i in range(n):
9       counts[arr[i]] += 1
10       if counts[arr[i]] > n/4:
11          return arr[i]
12    return -1

Alternate Java solution with a hash map

1
2java
3import java.util.HashMap;
4class Solution {
5  public int findSpecialInteger(int[] arr) {
6     HashMap<Integer, Integer> counts = new HashMap<>();
7     int n = arr.length;
8     for(int i = 0; i < n; i++) {
9        counts.put(arr[i], counts.getOrDefault(arr[i], 0) + 1);
10        if(counts.get(arr[i]) > n/4)
11           return arr[i];
12     }
13     return -1;
14  }
15}

Alternate JavaScript solution with a hash map

1
2javascript
3class Solution {
4  findSpecialInteger(arr) {
5    const counts = {};
6    const n = arr.length;
7    for(let i = 0; i < n; i++){
8      counts[arr[i]] = (counts[arr[i]] || 0) + 1;
9      if(counts[arr[i]] > n/4)
10        return arr[i];
11    }
12    return -1;
13  }
14}

Remember, the original method where we compare 'arr[i]' and 'arr[i+quarter]' works only on sorted arrays. In conclusion, the problem of finding an element that occurs more than 25% of the time in a non-decreasing array can be solved by scanning through the array once and recording counts or by comparing current element and future element separated by quarter of the length of the array.