# Find Number with More Than 25 Percent Frequency In Sorted Array

## Leetcode

1. Element Appearing More Than 25% In Sorted Array
``````class Solution(object):
def findSpecialInteger(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
if len(arr) > 8:
return self.getMostFrequentNumberOptimized(arr)

return self.getMostFrequentNumber(arr)

def getMostFrequentNumber(self, arr):
counter = {}

for n in arr:
if n in counter:
counter[n] += 1
else:
counter[n] = 1

targetPercent = (len(arr) * 25)//100

for n in counter:
if counter[n] > targetPercent:
return n

def getMostFrequentNumberOptimized(self, arr):
numsCount = len(arr)
p1 = (numsCount // 4) - 1
p2 = (numsCount // 2) - 1
p3 = ((numsCount * 3) // 4) - 1

print("len=", numsCount, "p1=", p1, "p2=", p2, "p3=", p3)
print(arr[0], arr[p1], arr[p2], arr[p3], arr[-1])

if arr[0] == arr[p1]:
return arr[0]

if arr[p1] == arr[p2]:
return arr[p1]

if arr[p2] == arr[p3]:
return arr[p2]

if arr[p3] == arr[-1]:
return arr[p3]
``````

The above optimized approach has a flaw. The offsets are fixed and the 25% spread can be across two quartets.

``````num = [1,2,2,2,3,4,4,5,6,6,7,7]
``````

We need to use a sliding window of quarters.

``````def getMostFrequentNumberOptimized(self, arr):
n = len(arr)
offset = n/4

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

### Reference

This site uses Akismet to reduce spam. Learn how your comment data is processed.