My soln in python


#1

I used dictionary/Hash tables but the solution got accepted. But the term constant additional space. means O(1) right???
here is my code

   def repeatedNumber(self, A):
        n = len(A)//3
        dictionary = {}
        for i in A:
            if i in dictionary:
                dictionary[i] += 1
            else:
                dictionary[i] = 1
        for key, value in dictionary.items():
            if value > n:
                return key
        return -1

#2

dictionary might be non constant in space