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

 
Constraints:

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

Source: leetcode | Difficulty: EASY
Tags: Data structures

Starter code: class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        

Solutions:
class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		count = 0
		num = arr[0]
		for x in arr:
			if x == num:
				count = count + 1
			elif x != num and count / len(arr) > 0.25:
				return num
			else:
				num = x
				count = 1
		return arr[len(arr) - 1]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		n = len(arr) // 4
		for i in range(len(arr)):
			if arr[i] == arr[i + n]:
				return arr[i]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		a = list(set(arr))
		print(a)
		per = 0
		i = 0
		while per <= 0.25:
			b = a[i]
			per = arr.count(a[i]) / len(arr)
			i += 1
		return b


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for i in set(arr):
			if arr.count(i) > 0.25 * len(arr):
				return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		setter = set(arr)
		a_fourth = len(arr) / 4
		for elem in setter:
			if arr.count(elem) > a_fourth:
				return elem


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		s = set(arr)
		perc_val = 0.25 * len(arr)
		for e in s:
			if arr.count(e) > perc_val:
				return e


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		x = len(arr) / 4
		i = 0
		while i < len(arr):
			y = arr.count(arr[i])
			print(i)
			if y > x:
				return arr[i]
			i += y


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		x = len(arr) / 4
		for i in arr:
			y = arr.count(i)
			if y > x:
				return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for num in set(arr):
			if arr.count(num) / len(arr) * 100 > 25:
				return num


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		arrlen = len(arr)
		arrcnt = Counter(arr)
		for (key, val) in arrcnt.items():
			if val * 4 > arrlen:
				return key


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for i in set(arr):
			if arr.count(i) > len(arr) / 4:
				return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		sets = set(arr)
		for num in sets:
			s = arr.count(num)
			if s > len(arr) / 4:
				return num
		return None


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		unique_nums = list(dict.fromkeys(arr))
		for unique_num in unique_nums:
			if arr.count(unique_num) / len(arr) > 0.25:
				return unique_num


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		arrLen = len(arr)
		maxCount = 0
		maxCountNumber = 0
		arrDict = {}
		for i in range(arrLen):
			if arr[i] not in arrDict:
				arrDict[arr[i]] = i
				numCount = arr.count(arr[i])
				if numCount > maxCount:
					maxCountNumber = arr[i]
					maxCount = numCount
		return maxCountNumber


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		else:
			appear = -(-len(arr) // 4)
			dict = {}
			for i in arr:
				if i not in dict:
					dict[i] = 1
				else:
					dict[i] += 1
				if dict[i] > appear:
					return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		quarter = len(arr) / 4
		count = 0
		temp = []
		for item in arr:
			if item not in temp:
				temp.append(item)
		for item in temp:
			count = arr.count(item)
			if count > quarter:
				return item


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		unique_values = list()
		for i in range(0, len(arr)):
			if arr[i] not in unique_values:
				unique_values.append(arr[i])
		for j in range(0, len(unique_values)):
			if arr.count(unique_values[j]) / len(arr) > 0.25:
				return unique_values[j]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		k = list(set(arr))
		tmp = []
		size = len(arr)
		for i in k:
			tmp.append(arr.count(i))
		maximum = max(tmp)
		indexing = tmp.index(maximum)
		z = maximum / size * 100
		if z >= 25:
			return k[indexing]
		else:
			return 0


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		k = list(set(arr))
		tmp = []
		for i in k:
			tmp.append(arr.count(i))
		max1 = max(tmp)
		index = tmp.index(max1)
		print(k[index])
		if max1 > len(arr) / 4:
			return k[index]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		condensed = set(arr)
		counter = 0
		digit = 0
		print(condensed)
		for i in condensed:
			temp = arr.count(i)
			if counter < temp:
				counter = temp
				digit = i
		return digit


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		return max(set(arr), key=arr.count)


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for ar in arr:
			a = self.find(arr, ar, True)
			b = self.find(arr, ar, False)
			if b - a + 1 > len(arr) * 0.25:
				return ar

	def find(self, arr, value, fromLeft: bool):
		left = 0
		right = len(arr) - 1
		index = -1
		while left <= right:
			mid = (left + right) // 2
			midValue = arr[mid]
			if midValue == value:
				index = mid
				break
			if value < midValue:
				right = mid
			else:
				left = mid
		if fromLeft:
			while index > 0:
				if arr[index] == arr[index - 1]:
					index -= 1
				else:
					break
			return index
		else:
			while index < len(arr) - 1:
				if arr[index] == arr[index + 1]:
					index += 1
				else:
					break
			return index


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[-1]
		k = int(len(arr) // 4) + 1
		c = 1
		for i in range(1, len(arr)):
			if arr[i - 1] == arr[i]:
				c += 1
				if c >= k:
					return arr[i]
			else:
				c = 1


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		count = {}
		for num in arr:
			count[num] = count.get(num, 0) + 1
			if count[num] > len(arr) * 0.25:
				return num


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		rate = len(arr) // 4
		count = [0 for i in range(100001)]
		for (idx, value) in enumerate(arr):
			count[value] += 1
			if count[value] > rate:
				return value
		return 0


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		goal_count = len(arr) * 0.25
		temp_list = []
		for num in arr:
			if len(arr) == 1:
				return arr[0]
			elif len(temp_list) > goal_count:
				return temp_list[0]
			elif num in temp_list:
				temp_list.append(num)
			else:
				temp_list.clear()
				temp_list.append(num)
		return temp_list[0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		d = {}
		for num in arr:
			d[num] = d.get(num, 0) + 1
		for (idx, val) in d.items():
			if val > len(arr) * 0.25:
				return idx


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		arrLen = len(arr)
		delta = arrLen // 4
		if arrLen == 1:
			return arr[0]
		pre = ''
		i = 0
		while i < arrLen - delta:
			if arr[i] != pre:
				pre = arr[i]
				if arr[i + delta] == pre:
					return pre
			i += 1


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		limit = len(arr) // 4
		curr = arr[0]
		count = 1
		for i in range(1, len(arr)):
			if arr[i] != curr:
				curr = arr[i]
				count = 1
				continue
			else:
				count += 1
				if count > limit:
					return curr


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		if len(arr) <= 2:
			return arr[0]
		lim = len(arr) // 4
		count = 1
		for (num1, num2) in zip(arr, arr[1:]):
			if num1 == num2:
				count += 1
				if count > lim:
					return num1
			else:
				count = 1


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		if len(arr) == 0:
			return -1
		if len(arr) == 1:
			return arr[0]
		p1 = p2 = 0
		arrLen = len(arr)
		while p2 < arrLen:
			if arr[p2] != arr[p1]:
				if (p2 - p1) / arrLen > 0.25:
					return arr[p1]
				p1 = p2
			p2 += 1
		return arr[p2 - 1]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		num_dict = {}
		for num in arr:
			if num in num_dict:
				num_dict[num] += 1
			else:
				num_dict[num] = 1
		return max(num_dict, key=lambda k: num_dict[k])


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		count = 0
		maxCount = 0
		maxInt = arr[0]
		currInt = arr[0]
		for x in arr:
			if x != currInt:
				if count > maxCount:
					maxCount = count
					maxInt = currInt
				currInt = x
				count = 1
			else:
				count += 1
		if count > maxCount:
			maxCount = count
			maxInt = currInt
		return maxInt


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		d = Counter(arr)
		d = sorted(list(d.items()), key=lambda x: x[1], reverse=True)
		return d[0][0]


from collections import Counter

class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		n = len(arr)
		if n <= 9:
			return self.findMode(arr)
		c = [arr[0], arr[(n - 1) // 8], arr[2 * (n - 1) // 8], arr[3 * (n - 1) // 8], arr[4 * (n - 1) // 8], arr[5 * (n - 1) // 8], arr[6 * (n - 1) // 8], arr[7 * (n - 1) // 8], arr[n - 1]]
		return self.findMode(c)

	def findMode(self, arr: List[int]) -> int:
		return collections.Counter(arr).most_common(1)[0][0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		n = len(arr) / 4
		freq = {}
		for i in arr:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		for (k, v) in list(freq.items()):
			if v > n:
				return k


from collections import defaultdict

class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		counts = defaultdict(int)
		for i in arr:
			counts[i] += 1
		return max(counts.items(), key=lambda x: x[1])[0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		d = {}
		max1 = 0
		for i in arr:
			if i in d:
				d[i] = d[i] + 1
			else:
				d[i] = 1
			max1 = max(d[i], max1)
		for i in d:
			if d[i] == max1:
				return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		n = len(arr)
		threshold = n / 4.0
		print(threshold)
		oldnum = None
		for num in arr:
			if oldnum == num:
				count += 1
				if count > threshold:
					return num
			else:
				count = 1
				oldnum = num
		if count > threshold:
			return num


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		start = True
		d = 0
		count = 0
		if len(arr) == 1:
			return arr[0]
		for v in arr:
			if start:
				start = False
				d = v
				count = 1
			elif v == d:
				count += 1
				if len(arr) % 4 == 0 and count > len(arr) / 4:
					return v
				if len(arr) % 4 != 0 and count >= len(arr) // 4 + 1:
					return v
			else:
				d = v
				count = 1
		return 0


from collections import defaultdict

class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		count = 0
		thresh_count = int(0.25 * len(arr))
		dic = defaultdict(int)
		for ele in arr:
			dic[ele] += 1
			if dic[ele] > thresh_count:
				return ele


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		b = {}
		for a in arr:
			if a not in b:
				b[a] = 1
			else:
				b[a] += 1
		c = [[k, v] for (k, v) in sorted(b.items(), key=lambda item: item[1])]
		return c[-1][0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		count = [0] * 100001
		n = len(arr)
		for i in arr:
			count[i] += 1
		for i in range(len(count)):
			if count[i] > int(0.25 * n):
				return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		minCount = len(arr) // 4
		temp = 0
		pp = 0
		for i in range(len(arr)):
			if pp == arr[i]:
				temp += 1
			else:
				temp = 0
			if temp >= minCount:
				return arr[i]
			pp = arr[i]


import numpy as np

class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		return collections.Counter(arr).most_common(1)[0][0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		from scipy import stats
		x = stats.mode(arr)
		y = int(x[1]) * 100 / len(arr)
		if y > 25:
			return int(x[0])
s = Solution()
print(s.findSpecialInteger)


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		the_dict = {}
		for num in arr:
			the_dict[num] = the_dict.get(num, 0) + 1
		for item in list(the_dict.items()):
			if item[1] == max(the_dict.values()):
				return item[0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		cnt = collections.Counter(arr)
		for (k, v) in cnt.items():
			if v == max(cnt.values()):
				return k


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		from collections import Counter
		c = Counter(arr)
		for (i, j) in list(c.items()):
			if j == max(c.values()):
				return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		len1 = int(len(arr) * 0.25)
		count = 0
		sub = []
		for i in arr:
			if i not in sub:
				sub.append(i)
				count = 1
			else:
				count += 1
			if count > len1:
				return i


class Solution:
	from collections import Counter

	def findSpecialInteger(self, arr: List[int]) -> int:
		res = Counter(arr)
		ans = 0
		for (key, value) in list(res.items()):
			if value / sum(res.values()) > 0.25:
				ans = key
		return ans


from collections import Counter

class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		return [key for (key, value) in Counter(arr).items() if value > len(arr) // 4][0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		l = len(arr)
		bound = l / 4
		s = set()
		for i in arr:
			if i not in s:
				if arr.count(i) > bound:
					return i
				s.add(i)


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for i in range(len(arr)):
			if arr.count(arr[i]) / len(arr) > 0.25:
				s = arr[i]
				break
		return s


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		uniq = list()
		[uniq.append(i) for i in arr if i not in uniq]
		occurs = {i: 0 for i in arr}
		for i in arr:
			occurs[i] += 1
		return [key for (key, val) in list(occurs.items()) if val / len(arr) > 0.25][0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		elem = 0
		for ar in arr:
			if arr.count(ar) > int(0.25 * len(arr)):
				elem = ar
				break
		return elem


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for i in arr:
			x = arr.count(i)
			perc = float(x) / float(len(arr))
			if perc > 0.25:
				return i


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for n in arr:
			if arr.count(n) / len(arr) > 0.25:
				return n


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		quarter = len(arr) // 4
		count = 1
		for i in range(len(arr)):
			if i == len(arr) - 1:
				return arr[i]
			if arr[i] == arr[i + 1]:
				count += 1
				if count > quarter:
					return arr[i]
			else:
				count = 1


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		mark = len(arr) // 4
		for x in arr:
			if mark < arr.count(x):
				return x


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		l = len(arr)
		a = l // 4
		for i in arr:
			if arr.count(i) > a:
				return i
		return -1


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		largeArr = {}
		tempCount = 0
		for num in arr:
			if num in largeArr:
				tempCount = tempCount + 1
				largeArr[num] = tempCount
			else:
				tempCount = 1
				largeArr[num] = tempCount
		max1 = max(largeArr.values())
		for key in list(largeArr.keys()):
			if largeArr[key] == max(largeArr.values()):
				return key


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for i in arr:
			if arr.count(i) > len(arr) * 25 // 100:
				return i
				break


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		counts = dict()
		for i in arr:
			counts[i] = counts.get(i, 0) + 1
		return max(counts, key=counts.get)


class Solution:

	def findSpecialInteger(self, l: List[int]) -> int:
		for i in l:
			if l.count(i) > len(l) / 4:
				return i


class Solution:

	def findSpecialInteger(self, nums: List[int]) -> int:
		percent = len(nums) * 0.25
		for I in nums:
			if nums.count(I) > percent:
				return I


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		dic = Counter(arr)
		return [k for (k, v) in dic.items() if v == max(dic.values())][0]


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		threshold = len(arr) // 4
		numdic = {}
		for num in arr:
			if str(num) not in numdic:
				numdic[str(num)] = 1
			else:
				numdic[str(num)] += 1
			if numdic[str(num)] > threshold:
				return num


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		nums = list(set(arr))
		for i in nums:
			if arr.count(i) >= len(arr) // 4 + 1:
				return i
		return False


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		arr1 = set(arr)
		cutoff = len(arr) * 0.25
		for item in arr1:
			if arr.count(item) > cutoff:
				return item


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for num in arr:
			if arr.count(num) > len(arr) // 4:
				return num


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		count = 0.25 * len(arr)
		arr1 = list(set(arr))
		for ele in arr1:
			if arr.count(ele) > count:
				return ele


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		for item in set(arr):
			l = len(arr)
			if arr.count(item) > l / 4:
				return item


class Solution:

	def findSpecialInteger(self, arr: List[int]) -> int:
		a = len(arr) * 0.25
		value = 0
		a1 = int(a)
		print(a1)
		dict1 = {}
		for i in arr:
			dict1[i] = dict1.get(i, 0) + 1
		for i in arr:
			if dict1.get(i) > a1:
				value = i
		return value