Given an array arr[] of size N and an element k. The task is to find all elements in array that appear more than n/k times.
Example 1:
Input:
N = 8
arr[] = {3,1,2,2,1,2,3,3}
k = 4
Output: 2
Explanation: In the given array, 3 and
 2 are the only elements that appears 
more than n/k times.
Example 2:
Input:
N = 4
arr[] = {2,3,3,2}
k = 3
Output: 2
Explanation: In the given array, 3 and 2 
are the only elements that appears more 
than n/k times. So the count of elements 
are 2.
Your Task:
The task is to complete the function countOccurence() which returns count of elements with more than n/k times appearance.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{4}
1 <= a[i] <= 10^{6}
1 <= k <= N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3





class Solution:

    

    #Function to find all elements in array that appear more than n/k times.

    def countOccurence(self,arr,n,k):

        #Your code here

Solutions:
class Solution:

	def countOccurence(self, arr, n, k):
		x = n / k
		c = 0
		times = []
		nums = []
		for i in range(n):
			if arr[i] not in nums:
				nums.append(arr[i])
				times.append(1)
			else:
				ind = nums.index(arr[i])
				times[ind] += 1
		for l in times:
			if l > x:
				c = c + 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		res = 0
		for (kl, v) in d.items():
			if v > n / k:
				res += 1
		return res


class Solution:

	def countOccurence(self, arr, n, k):
		h = {}
		for i in arr:
			if i not in h:
				h[i] = 1
			else:
				h[i] += 1
		ans = 0
		for val in h.values():
			if val > n / k:
				ans += 1
		return ans


class Solution:

	def countOccurence(self, arr, n, k):
		lim = n // k
		b = dict()
		j = 0
		for i in arr:
			if i not in b.keys():
				b[i] = 1
			else:
				b[i] += 1
		for i in b.values():
			if i > lim:
				j += 1
		return j


class Solution:

	def countOccurence(self, arr, n, k):
		c = 0
		d = []
		for i in arr:
			if arr.count(i) > n / k and i not in d:
				c += 1
				d.append(i)
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		count = 0
		d = dict()
		for i in arr:
			d[i] = d.get(i, 0) + 1
		if k == n:
			return len(d)
		else:
			for i in d.values():
				if i > n / k:
					count += 1
			return count


class Solution:

	def countOccurence(self, arr, n, k):
		count = 0
		s = {}
		for i in arr:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		for a in s:
			if s[a] > n // k:
				count = count + 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		m = n // k
		cntDict = dict()
		for i in arr:
			if i in cntDict:
				cntDict[i] += 1
			else:
				cntDict[i] = 1
		cnt = 0
		for i in cntDict.keys():
			if cntDict[i] > m:
				cnt += 1
		return cnt


class Solution:

	def countOccurence(self, arr, n, k):
		cnt = n / k
		repeat_dict = {}
		out = 0
		for i in arr:
			if i in repeat_dict.keys():
				repeat_dict[i] += 1
			else:
				repeat_dict[i] = 1
		for i in repeat_dict.keys():
			if repeat_dict[i] > cnt:
				out += 1
		return out


class Solution:

	def countOccurence(self, arr, n, k):
		hash_map = {}
		count = 0
		for item in arr:
			hash_map[item] = hash_map.get(item, 0) + 1
		for (_, value) in hash_map.items():
			if value > n / k:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		r = n // k
		b = []
		for p in arr:
			if arr.count(p) > r:
				b.append(p)
		return len(list(set(b)))


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		v = n / k
		count = 0
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for (key, values) in d.items():
			if d[key] > v:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		has = {}
		c = 0
		for i in range(len(arr)):
			if arr[i] in has:
				has[arr[i]] += 1
			else:
				has[arr[i]] = 1
		for j in has:
			if has[j] > n // k:
				c += 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		m = n // k
		count = 0
		for i in set(arr):
			ans = arr.count(i)
			if ans > m:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		count = 0
		dict1 = {}
		for i in arr:
			if i not in dict1:
				dict1[i] = 0
			dict1[i] += 1
		for i in dict1:
			if dict1[i] > n // k:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		d = n // k
		f = 0
		c = {}
		for i in arr:
			if i in c:
				c[i] += 1
			else:
				c[i] = 1
		for i in c:
			if c[i] > d:
				f += 1
		return f


class Solution:

	def countOccurence(self, arr, n, k):
		a = n // k
		d = {}
		c = 0
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for (x, y) in d.items():
			if y > a:
				c += 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		hashm = {}
		cnt = 0
		k = n / k
		for i in range(len(arr)):
			if arr[i] not in hashm:
				hashm[arr[i]] = 1
			else:
				hashm[arr[i]] += 1
		keys = hashm.keys()
		for i in keys:
			if hashm[i] > k:
				cnt += 1
		return cnt


from collections import Counter

class Solution:

	def countOccurence(self, arr, n, k):
		ans = Counter(arr)
		count = 0
		for (i, j) in ans.items():
			if j > n // k:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		x = n / k
		l = []
		for i in arr:
			if arr.count(i) > x:
				l.append(i)
		l = set(l)
		return len(l)


class Solution:

	def countOccurence(self, arr, n, k):
		dict = {}
		k = n / k
		for i in arr:
			if i not in dict:
				dict[i] = 1
			else:
				dict[i] += 1
		a2 = list(dict.values())
		count = 0
		for i in a2:
			if i > k:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		a = n / k
		dict = {}
		c = 0
		for i in range(n):
			if arr[i] in dict:
				dict[arr[i]] = dict[arr[i]] + 1
			else:
				dict[arr[i]] = 1
		for i in dict:
			if dict[i] > a:
				c = c + 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		d = dict(())
		for i in arr:
			d[i] = d.get(i, 0) + 1
		r = n / k
		c = 0
		for (key, value) in d.items():
			if value > r:
				c = c + 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		a = []
		l = 0
		l = int(l)
		l = n // k
		d = {i: 0 for i in arr}
		for i in arr:
			if i in d:
				d[i] = d[i] + 1
			else:
				d[i] = 1
		for i in d:
			if d[i] > l:
				a.append(i)
		return len(a)


class Solution:

	def countOccurence(self, arr, n, k):
		s = n // k
		l = list(set(arr))
		count = 0
		for i in l:
			if arr.count(i) > s:
				count = count + 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		a = n // k
		l = []
		m = list(set(arr))
		for i in range(len(m)):
			d[m[i]] = arr.count(m[i])
		for (key, values) in d.items():
			if values > a:
				l.append(values)
		return len(l)


class Solution:

	def countOccurence(self, arr, n, k):
		n2 = n / k
		count1 = 0
		res = []
		res = []
		for i in arr:
			count = arr.count(i)
			if count > n2 and i not in res:
				res.append(i)
				count1 = count1 + 1
		return count1


class Solution:

	def countOccurence(self, arr, n, k):
		import collections
		dic = collections.Counter(arr)
		req = n / k
		ct = 0
		for v in dic.values():
			if v > req:
				ct += 1
		return ct


from collections import Counter

class Solution:

	def countOccurence(self, arr, n, k):
		count = Counter(arr)
		return len([i for i in count.items() if i[1] > n / k])


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		for i in range(len(arr)):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		p = 0
		for i in d:
			if d[i] > n / k:
				p += 1
		return p


class Solution:

	def countOccurence(self, arr, n, k):
		dic = dict()
		ans = 0
		threshold = n // k
		for x in arr:
			if x not in dic:
				dic[x] = 0
			dic[x] += 1
		for key in dic.keys():
			if dic[key] > threshold:
				ans += 1
		return ans


class Solution:

	def countOccurence(self, arr, n, k):
		(d, c, t) = ({}, 0, n // k)
		for i in arr:
			if i not in d:
				d[i] = 0
			d[i] += 1
		for i in d:
			if d[i] > t:
				c += 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		arr.sort()
		x = 1
		y = 0
		for i in range(0, n - 1):
			if arr[i] == arr[i + 1]:
				x = x + 1
			else:
				if x > n // k:
					y = y + 1
				x = 1
		if x > n // k:
			y = y + 1
		return y


from collections import Counter

class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		l = []
		c = 0
		d = Counter(arr)
		for (ke, value) in d.items():
			if value > n // k:
				c += 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		s = n // k
		new = []
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for (key, v) in dic.items():
			if v > s:
				new.append(key)
		return len(new)


class Solution:

	def countOccurence(self, arr, n, k):
		arr.sort()
		x = int(n // k)
		a = 0
		i = 0
		while i < len(arr):
			count = 1
			while i + 1 < len(arr) and arr[i] == arr[i + 1]:
				count += 1
				i = i + 1
			if count > x:
				a += 1
			i = i + 1
		return a


class Solution:

	def countOccurence(self, arr, n, k):
		dic = {}
		for r in arr:
			if r in dic:
				dic.update({r: dic.get(r) + 1})
			else:
				dic.update({r: 1})
		count = 0
		for r in dic:
			if dic.get(r) > n / k:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		c = 0
		t = n // k
		p = 0
		arr.sort()
		for i in range(0, n - 1):
			if arr[i] == arr[i + 1]:
				c += 1
				if c == t:
					p += 1
			else:
				c = 0
		return p


from collections import Counter

class Solution:

	def countOccurence(self, arr, n, k):
		c = Counter(arr)
		a = 0
		for i in c.keys():
			if c[i] > n // k:
				a += 1
		return a


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		l = []
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		for i in range(n):
			if d[arr[i]] > n / k:
				l.append(arr[i])
		return len(set(l))


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		count = 0
		for j in d:
			if d[j] > n // k:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		d = n / k
		b = []
		for i in arr:
			if arr.count(i) > d:
				b.append(i)
		return len(set(b))


class Solution:

	def countOccurence(self, arr, n, k):
		dict = {}
		for i in arr:
			dict[i] = dict.get(i, 0) + 1
		count = 0
		for i in dict:
			if dict[i] > n // k:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		occ = n / k
		count = 0
		dict = {}
		for i in arr:
			if i not in dict.keys():
				dict[i] = 1
			else:
				dict[i] = dict[i] + 1
		for i in dict.keys():
			if dict[i] > occ:
				count = count + 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		for i in range(n):
			d[arr[i]] = arr.count(arr[i])
		key = []
		for key1 in d.values():
			key.append(key1)
		count1 = 0
		for i in key:
			if i > n / k:
				count1 = count1 + 1
		return count1


from collections import defaultdict

class Solution:

	def countOccurence(self, a, n, k):
		dic = defaultdict(int)
		ans = 0
		for i in range(n):
			dic[a[i]] += 1
			if dic[a[i]] > n // k:
				ans += 1
				dic[a[i]] = -10 ** 9
		return ans


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] = d[i] + 1
		c = 0
		for (key, value) in d.items():
			if d[key] > n / k:
				c = c + 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		l = n / k
		res = {}
		count = 0
		for i in arr:
			if i not in res:
				res[i] = 1
			else:
				res[i] += 1
		for i in res:
			if res[i] > l:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		d = dict()
		count = 0
		v = n / k
		for i in range(n):
			if arr[i] in d.keys():
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		for j in d.values():
			if j > v:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		a = n // k
		c = 0
		arr1 = list(set(arr))
		for k in arr1:
			if arr.count(k) > a:
				c += 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		num_count = dict()
		for num in arr:
			if num in num_count:
				num_count[num] += 1
			else:
				num_count[num] = 1
		n_over_k = n / k
		count = 0
		for num in num_count:
			if num_count[num] > n_over_k:
				count += 1
		return count


from collections import Counter

class Solution:

	def countOccurence(self, arr, n, k):
		count = Counter(arr)
		s = 0
		appear = n // k
		for (key, value) in count.items():
			if value > appear:
				s += 1
		return s


class Solution:

	def countOccurence(self, arr, n, k):
		import collections
		freqs = collections.Counter(arr)
		c = 0
		for (u, v) in freqs.items():
			if v > n / k:
				c += 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		dic = {}
		cnt = 0
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for (key, value) in dic.items():
			if value > n // k:
				cnt += 1
		return cnt


class Solution:

	def countOccurence(self, arr, n, k):
		bar = n // k
		arr.sort()
		prev = arr[0]
		cnt = 1
		greater = 0
		for i in range(1, n):
			if arr[i] == prev:
				cnt += 1
			else:
				if cnt > bar:
					greater += 1
				prev = arr[i]
				cnt = 1
		if cnt > bar:
			greater += 1
		return greater


class Solution:

	def countOccurence(self, arr, n, k):
		d = {}
		c = 0
		for i in range(n):
			d[arr[i]] = d.get(arr[i], 0) + 1
		for i in d.keys():
			if d[i] > n // k:
				c += 1
		return c


from collections import Counter

class Solution:

	def countOccurence(self, arr, n, k):
		b = n // k
		d = dict(Counter(arr))
		c = 0
		for i in d:
			if d[i] > b:
				c = c + 1
		return c


class Solution:

	def countOccurence(self, arr, n, k):
		seen = dict()
		count = 0
		occur = n // k
		for i in range(n):
			if arr[i] in seen:
				seen[arr[i]] += 1
			else:
				seen[arr[i]] = 1
		for key in seen:
			if seen[key] > occur:
				count += 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		dic = {}
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = 1
			else:
				h = dic[arr[i]]
				dic.update({arr[i]: h + 1})
		m = n / k
		count = 0
		for j in dic:
			if dic[j] > m:
				count = count + 1
		return count


class Solution:

	def countOccurence(self, arr, n, k):
		dic = {}
		for i in arr:
			if i in dic.keys():
				dic[i] = dic[i] + 1
			else:
				dic[i] = 1
		res = 0
		for i in dic.keys():
			if dic[i] > n // k:
				res += 1
		return res


from collections import Counter

class Solution:

	def countOccurence(self, arr, n, k):
		dic = Counter(arr)
		occur = n / k
		count = 0
		for (key, value) in dic.items():
			if value > occur:
				count += 1
		return count