Python | Check if k occurs atleast n times in a list
There are many common problems that a developer or common programmer comes across in day-day coding. One such problem is finding if an element occurs more than a certain number of times in the list. Let’s discuss certain ways to deal with this problem.
Method #1 : Using sum() + list comprehension The list comprehension can be clubbed with the sum function for achieving this particular task. The sum function does the summation part and the logical case of returning true is dealt in list comprehension part.
Python3
# Python3 code to demonstrate # check for minimum N occurrences of K # using sum() + list comprehension # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 # using sum() + list comprehension # checking occurrences of K atleast N times res = 0 res = sum ([ 1 for i in test_list if i = = k]) > = N if res = = 1 : res = True else : res = False # printing result print ( "Does %d occur atleast %d times ? :" % (k, N) + str (res)) |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur atleast 3 times ? :True
Method #2 : Using next() + islice() These both functions can be used together to perform this particular task in more efficient manner than above. The islice function would handle the summation part and next function helps with iteration logic.
Python3
# Python3 code to demonstrate # check for minimum N occurrences of K # using next() + islice() from itertools import islice # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ("The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 # using next() + islice() # checking occurrences of K atleast N times func = ( True for i in test_list if i = = k) res = next (islice(func, N - 1 , None ), False ) # printing result print ("Does % d occur atleast % d times ? :" % (k, N) + str (res)) |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur atleast 3 times ? : True
Method #3: Using count()
Python3
# Python3 code to demonstrate # check for minimum N occurrences of K # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 # checking occurrences of K atleast N times res = False if (test_list.count(k)> = N): res = True # printing result print ( "Does %d occur atleast %d times ? : " % (k, N) + str (res)) |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur atleast 3 times ? : True
Method #4 : Using for loop
Python3
# Python3 code to demonstrate # check for minimum N occurrences of K # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 # checking occurrences of K atleast N times res = False c = 0 for i in test_list: if (i = = k): c + = 1 if (c> = N): res = True # printing result print ( "Does %d occur atleast %d times ? : " % (k, N) + str (res)) |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur atleast 3 times ? : True
Time Complexity: O(n), where n is length of test_list.
Auxiliary Space: O(1)
Method #5 : Using operator.countOf() method
Python3
# Python3 code to demonstrate # check for minimum N occurrences of K import operator as op # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 # checking occurrences of K atleast N times res = False if (op.countOf(test_list, k) > = N): res = True # printing result print ( "Does %d occur atleast %d times ? : " % (k, N) + str (res)) |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur atleast 3 times ? : True
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #6: Using the itertools.groupby function
Python3
import itertools # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 # using the itertools.groupby function res = any ( len ( list (g)) > = N for _, g in itertools.groupby(test_list) if _ = = k) # printing result print ( "Does %d occur atleast %d times ? : " % (k, N) + str (res)) #This code is contributed by Vinay Pinjala. |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur atleast 3 times ? : False
Time Complexity: O(n)
Auxiliary Space: O(1)
Method#7: Using Recursive method.
The algorithm is as follows:
- Check if the input list is empty or N is zero. If either of the conditions is true, return False.
- Check if the first element of the list is K. If it is, decrement N and recurse on the rest of the list.
- If the first element of the list is not K, recurse on the rest of the list with the same N.
- If N becomes zero at any point, return True.
- If the entire list has been processed and N is still not zero, return False.
Python3
def check_occurrences(lst, K, N): # Base case: if the list is empty or N is zero, return False if not lst or N = = 0 : return False # Recursive case: check if the first element of the list is K if lst[ 0 ] = = K: # If it is, decrement N and recurse on the rest of the list return check_occurrences(lst[ 1 :], K, N - 1 ) else : # If it's not, recurse on the rest of the list with the same N return check_occurrences(lst[ 1 :], K, N) # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 res = check_occurrences(test_list, k, N) # printing result print ( "Does %d occur atleast %d times ? : " % (k, N) + str (res)) #This code is contributed by tvsk. |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur atleast 3 times ? : False
The time complexity of the algorithm is O(n), where n is the length of the input list. In the worst case, the algorithm will have to check all the elements of the list.
The auxiliary space complexity of the algorithm is O(n), where n is the length of the input list. This is because in the worst case, the algorithm will have to recurse n times, which will result in n function calls on the call stack.
Method#8: Using reduce():
Algorithm:
- Define a function check_occurrences(lst, K, N) that takes a list lst, an integer K, and an integer N as input.
- Check the base case. If the list is empty or N is zero, return False.
- Otherwise, use the reduce function to count the number of occurrences of K in the list.
- Return True if the count is greater than or equal to N, otherwise return False.
- Initialize a list and the variables k and N.
- Call the function check_occurrences() with the list, k, and N.
- Print the result.
Python3
from functools import reduce def check_occurrences(lst, K, N): return reduce ( lambda count, x: count + 1 if x = = K else count, lst, 0 ) > = N # initializing list test_list = [ 1 , 3 , 5 , 5 , 4 , 5 ] # printing original list print ( "The original list is : " + str (test_list)) # initializing k k = 5 # initializing N N = 3 res = check_occurrences(test_list, k, N) # printing result print ( "Does %d occur at least %d times? : " % (k, N) + str (res)) #This code is contrinuted by Pushpa. |
The original list is : [1, 3, 5, 5, 4, 5] Does 5 occur at least 3 times? : True
Time Complexity: O(N), where N is the length of the input list.
Space Complexity: O(1), since we only use a constant amount of extra space.
Contact Us