Given a list, the task is to find whether any element occurs ‘n’ times in given list of integers. It will basically check for the first element that occurs n number of times.
Examples:
Input: l = [1, 2, 3, 4, 0, 4, 3, 2, 1, 2], n = 3 Output : 2 Input: l = [1, 2, 3, 4, 0, 4, 3, 2, 1, 2, 1, 1], n = 4 Output : 1
Below are some methods to do the task in Python –
Method 1: Using Simple Iteration and Sort
Python3
# Python code to find occurrence of any element # appearing 'n' times# Input Initialisationinput = [1, 2, 3, 0, 4, 3, 4, 0, 0]# Sort Inputinput.sort()# Constants Declarationn = 3prev = -1count = 0flag = 0# Iteratingfor item in input: if item == prev: count = count + 1 else: count = 1 prev = item if count == n: flag = 1 print("There are {} occurrences of {} in {}".format(n, item, input)) break# If no element is not found.if flag == 0: print("No occurrences found") |
Output
There are 3 occurrences of 0 in [0, 0, 0, 1, 2, 3, 3, 4, 4]
Time complexity: O(n*logn), as sort() function is used.
Auxiliary space: O(1)
Method 2: Using Count
Python3
# Python code to find occurrence of any element # appearing 'n' times# Input list initialisationinput = [1, 2, 3, 4, 0, 4, 3, 4]# Constant declarationn = 3# printprint("There are {} occurrences of {} in {}".format(input.count(n), n, input)) |
Output
There are 2 occurrences of 3 in [1, 2, 3, 4, 0, 4, 3, 4]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(1), as only a constant amount of extra space is used.
Method 3: Using defaultdict
We first populate item of list in a dictionary and then we find whether count of any element is equal to n.
Python3
# Python code to find occurrence of any element # appearing 'n' times# importingfrom collections import defaultdict# Dictionary declarationdic = defaultdict(int)# Input list initialisationInput = [9, 8, 7, 6, 5, 9, 2]# Dictionary populatefor i in Input: dic[i]+= 1# constant declarationn = 2flag = 0# Finding from dictionaryfor element in Input: if element in dic.keys() and dic[element] == n: print("Yes, {} has {} occurrence in {}.".format(element, n, Input)) flag = 1 break# if element not found.if flag == 0: print("No occurrences found") |
Output
Yes, 9 has 2 occurrence in [9, 8, 7, 6, 5, 9, 2].
Method #4 : Using Counter() function
Python3
# Python code to find occurrence of any element# appearing 'n' times# importingfrom collections import Counter# Input list initialisationInput = [9, 8, 7, 6, 5, 9, 2]freq = Counter(Input)# constant declarationn = 2if n in freq.values(): for key, value in freq.items(): if(value == n): print("Yes, {} has {} occurrence in {}.".format(key, n, Input))# if element not found.else: print("No occurrences found") |
Output
Yes, 9 has 2 occurrence in [9, 8, 7, 6, 5, 9, 2].
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#5:Using regular expressions
Python3
import re# Input list initialisationinput_list = [9, 8, 7, 6, 5, 9, 2]# constant declarationn = 2occurrences = {}for item in input_list: occurrences[item] = occurrences.get(item, 0) + 1result = [item for item, count in occurrences.items() if count == n]if result: print("Yes, {} has {} occurrence in {}.".format(result[0], n, input_list))else: print("No items appear {} times in the input list".format(n))#This code is contributed by Vinay Pinjala. |
Output
Yes, 9 has 2 occurrence in [9, 8, 7, 6, 5, 9, 2].
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#6: Using Recursive method.
Python3
def count_occurrences(input_list, item, n): if not input_list: return False if input_list[0] == item: n -= 1 if n == 0: return True return count_occurrences(input_list[1:], item, n)def main(): input_list = [9, 8, 7, 6, 5, 9, 2] n = 2 for item in set(input_list): if count_occurrences(input_list, item, n): print("Yes, {} has {} occurrence in {}.".format(item, n, input_list)) return print("No items appear {} times in the input list".format(n))if __name__ == '__main__': main()#this code contributed by tvsk |
Output
Yes, 9 has 2 occurrence in [9, 8, 7, 6, 5, 9, 2].
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #7 : Using operator.countOf() method
Approach
- Convert the list to a unique value list using set(), and list().
- Check the unique element count in the original list is equal to N or not, If equal print(“There are {} occurrences of {} in {}”.format(n, i , input)), Otherwise, print(“No occurrences found”)
Python3
# Python code to find occurrence of any element# appearing 'n' timesimport operator# Input list initialisationinput = [9, 8, 7, 6, 5, 9, 2]# Constant declarationn = 2x = list(set(input))res = Falsefor i in x: if(operator.countOf(input, i) == n): print("There are {} occurrences of {} in {}".format(n, i, input)) res = True break if(not res): print("No occurrences found") |
Output
There are 2 occurrences of 9 in [9, 8, 7, 6, 5, 9, 2]
Time Complexity: O(N)
Auxiliary Space: O(1)
