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

Difficulty: introductory

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:
        len_25 = len(arr) * .25
        for item in set(arr):
            if arr.count(item) > len_25:
                return item

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:
        for i in arr:
            if arr.count(i) > len(arr) / 4:
                return i


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:
        temp=list(set(arr))
        for i in range(len(temp)):
            if (arr.count(temp[i]))/len(arr)>0.25:
                return temp[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:
        val = len(arr)*0.25
        for i in set(arr):
            if arr.count(i)>val:
                return i
                break


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:
        x=len(arr)/4
        i=0
        while i<len(arr):
            y=arr.count(arr[i])
            if y>x:
                return arr[i]
            i+=y
    
        
        
        


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


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))

#print(k)

        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:
        '''
        # fisrt solution
        if len(arr)==1: return arr[0]
        step = 1 if len(arr)<8 else len(arr)//4        
        for i in range(len(arr)):
            if arr[i]==arr[i+step]: return arr[i]
        '''
        return max(set(arr), key = arr.count)

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

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) *.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
        
        # print(len(arr), limit)
        
        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:
        # get 25% length of arr.
        div = len(arr) // 4
        # go through array and use div to check if an element spans to that length, if it does, special integer found.
        for i in range(len(arr) - div):
            if arr[i] == arr[i + div]:
                return arr[i]

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]


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]
        


from collections import Counter
class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        # def bin_search_variant(low, high, prev_val):
        #     mid = (high - low) // 2
        #     if arr[mid] == prev_val:
        #         return prev_val
        #     elif arr[mid]:
#         if len(arr) == 1 or len(arr) == 2 or len(arr) == 3:
#             return arr[0]
        
#         cntr = Counter(arr).items()
#         for k, v in cntr:
#             if v > len(arr) / 4:
#                 return k
        
        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:
        # this findMode can be furthur optimized given the input is also non-descending
        return collections.Counter(arr).most_common(1)[0][0]
                    


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


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:
            # print (oldnum, num)
            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
            else:
                if 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(.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]
                
        
        
        
        # from collections import Counter
        # c = Counter(arr)
        # return list(c.most_common(1))[0][0]


import numpy as np
class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        # temp=np.unique(arr)
        # le = len(arr)
        # for i in temp:
        #     if (arr.count(i)/le>0.25):
        #         return i
        return collections.Counter(arr).most_common(1)[0][0]
        # print(collections.Counter(arr).most_common(1))


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
#         p = len(arr)*0.25
        c = Counter(arr)
#         for i,j in c.items():
#             if float(j) > p:
#                 return i
        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: # counters or 2 pointers
    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: # 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:
            if arr.count(i) > len(arr)//4:
                return i

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


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


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:
        for i in arr:
            if float(arr.count(i)/len(arr))>0.25:
                return i
        
                
            


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


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


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:
        for i in arr:
            if float(arr.count(i)/len(arr))>0.25:
                return i

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, arr: List[int]) -> int:
        cnt = len(arr) * 0.25
        for i in arr:
            if arr.count(i) > cnt:
                return i

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

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:
        for i in arr:
            if arr.count(i)/len(arr) > 0.25:
                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)     #-- to remove duplicate for iteration purpose only
        
        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 set(arr):
            if arr.count(num)/len(arr) > 0.25:
                return num

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:
        unique = set(arr)
        for i in unique:
            if arr.count(i) > len(arr)//4:
                return i

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

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

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


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

        for n in set(arr):
            if arr.count(n) > len(arr) * 0.25:
                return n



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


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

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        len_arr = len(arr)

        for n in set(arr):
            if arr.count(n) > len_arr * 0.25:
                return n