Given an array of integers having n elements, return the numbers that occur more than floor(n/3) times in that array in increasing order. 
Example 1:
Input: arr[] = {1, 2, 1, 3, 1, 2}
Output: 1
Explanation:
Here we have 3 diffrent type of element 
1, 2 and 3. Now, You can count the frequency 
of all the elements
1 -> 3
2 -> 2
3 -> 1 
So, the only element which have frequency
greater than  ⌊n/3⌋ is {1}.
Example 2:
Input: arr[] = {1, 2, 2, 3, 2, 3, 2, 3} 
Output: 2 3
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function compute() that takes an array (arr), sizeOfArray (n), and return the array of the elements that occur more than ⌊n/3⌋ times in increasing order. The driver code automatically returns -1 in case of no elements ocuring more than ⌊n/3⌋ times.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def compute(self,arr, n) : 

        #Complete the function

Solutions:
class Solution:

	def compute(self, arr, n):
		d = {}
		res = []
		comp = n // 3
		for elem in arr:
			d.update({elem: d.get(elem, 0) + 1})
			if d[elem] > comp:
				res.append(elem)
				d[elem] = float('-inf')
		res.sort()
		return res if res else [-1]


from collections import defaultdict

class Solution:

	def compute(self, arr, n):
		store = defaultdict(lambda : 0)
		for item in arr:
			store[item] += 1
		output = []
		for item in store:
			if store[item] > n / 3:
				output.append(item)
		return sorted(output)


class Solution:

	def compute(self, arr, n):
		d = {}
		l = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] > n // 3:
				l.append(i)
		l.sort()
		return l


class Solution:

	def compute(self, arr, n):
		dict = {}
		for i in range(len(arr)):
			dict[arr[i]] = dict.get(arr[i], 0) + 1
		arr = list(set(arr))
		arr.sort()
		result = []
		for i in range(len(arr)):
			if dict[arr[i]] > n // 3:
				result.append(arr[i])
		if len(result) > 0:
			return result
		return [-1]


class Solution:

	def compute(self, arr, n):
		v = []
		arr.sort()
		x = n - n // 3
		current = ''
		for i in range(x):
			if arr[i] != current and arr[i] == arr[i + n // 3]:
				v.append(arr[i])
				current = arr[i]
		return v


class Solution:

	def compute(self, arr, n):
		f = n // 3
		m = {}
		for i in arr:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		l = []
		for i in m:
			if m[i] > f:
				l.append(i)
		l.sort()
		return l


class Solution:

	def compute(self, arr, n):
		d = {}
		target = n // 3
		ans = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for k in d:
			if d[k] > target:
				ans.append(k)
		ans.sort()
		return ans


class Solution:

	def compute(self, arr, n):
		size = n
		m = {}
		a = []
		for i in range(size):
			if arr[i] in m:
				m[arr[i]] += 1
			else:
				m[arr[i]] = 1
		flag = 0
		for i in sorted(m):
			if m[i] > int(size / 3):
				flag = 1
				a.append(i)
		if flag == 0:
			return [-1]
		else:
			return list(a)


class Solution:

	def compute(self, arr, n):
		j = {}
		for i in arr:
			if i in j:
				j[i] += 1
			else:
				j[i] = 1
		out = []
		for (num, val) in zip(j, list(j.values())):
			out = out + [(val, num)]
		out.sort()
		out = [i[1] for i in out if i[0] > int(n / 3)]
		out.sort()
		return out


import math

class Solution:

	def compute(self, arr, n):
		limit = math.floor(n / 3)
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		ans = []
		for i in dic:
			if dic[i] > limit:
				ans.append(i)
		return sorted(ans)