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.

&nbsp;
Example 1:

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


Example 2:

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


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 104
	0 &lt;= arr[i] &lt;= 105


class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        l=len(arr)
        c=(l//4)+1
        d={}
        for i in arr:
            if i in d:
                d[i]+=1
            else:
                d[i]=1
            if d[i]>=c:
                return i
class Solution {
     public int findSpecialInteger(int[] arr) {
        if (arr.length == 1) {
            return arr[0];
        }
        int count = (int) Math.ceil(arr.length / 4);
        System.out.println(count);

        Map<Integer, Integer> map = new HashMap<>();

        for (Integer i : arr) {
            map.put(i, map.getOrDefault(i, 0) + 1);
            if (map.get(i) > count) {
                return i;
            }
        }
        return -1;
    }
}
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        
        int freq = 0.25 * arr.size();
        map<int,int>m;
        for(int i: arr)
            m[i]++;
        
        int k;
        for(auto i: m)
        {
            if(i.second > freq)
            {
              k = i.first;
                break;
            }
        }
        return k;
    }
};
function binarySearch(array, target, findFirst) {
    function helper(start, end) {
        if (start > end) {
            return -1;
        }       
        
        const middle = Math.floor((start + end) / 2);
        const value = array[middle];
        
        if (value === target) {
            if (findFirst) {
                if (middle === 0 || array[middle - 1] !== value) {
                    return middle;
                }
                
                return helper(start, middle - 1);
            } else {
                if (middle === array.length -1 || array[middle + 1] !== value) {
                    return middle;
                }
                
                return helper(middle + 1, end);
            }
        } else if (value < target) {
          return helper(middle + 1, end);    
        }
        
        return helper(start, middle - 1);
    }
    
    return helper(0, array.length - 1)
}

const findFirstOccurance = (array, target) => binarySearch(array, target, true);
const findLastOccurance = (array, target) => binarySearch(array, target, false);

var findSpecialInteger = function(arr) {
    for (const i of [Math.floor(arr.length / 4), Math.floor(arr.length / 2), Math.floor(3 * arr.length / 4)]) {
        const firstOccurance = findFirstOccurance(arr, arr[i]);
        const lastOccurance = findLastOccurance(arr, arr[i]);
                
        if (lastOccurance - firstOccurance + 1 > arr.length / 4) {
            return arr[i]
        }
    }
    
    return -1;
};
Element Appearing More Than 25% In Sorted Array