Given a Tuple list, extract all with product greater than K.
Input : test_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)], K = 50 Output : [(4, 5, 7), (8, 4, 2)] Explanation : 140 and 64 are greater than 50, hence tuples extracted.
Input : test_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)], K = 100 Output : [(4, 5, 7)] Explanation : 140 is greater than 100, hence tuple extracted.
Method #1: Using list comprehension
In this, we extract all the tuples, greater than ‘K’ product using an external function.
Python3
# Python3 code to demonstrate working of# Filter Tuples Product greater than K# Using list comprehension# getting productdef prod(box): res = 1 for ele in box: res *= ele return res# initializing listtest_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)]# printing original listprint("The original list is : " + str(test_list))# Initializing KK = 50res = [sub for sub in test_list if prod(sub) > K]# Printing resultprint("Tuples with product greater than K : " + str(res)) |
The original list is : [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)] Tuples with product greater than K : [(4, 5, 7), (8, 4, 2)]
Time complexity: O(n*m), where n is the number of tuples in the list and m is the number of elements in each tuple.
Auxiliary space: O(1), as the space used is only for variables and not dependent on the size of input.
Method #2 : Using filter() + lambda
In this, the task of filtering tuples is done using filter() and lambda, product is computed in a similar way.
Python3
# Python3 code to demonstrate working of# Filter Tuples Product greater than K# Using filter() + lambda# Getting productdef prod(box): res = 1 for ele in box: res *= ele return res# Initializing listtest_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)]# Printing original listprint("The original list is : " + str(test_list))# Initializing KK = 50# Getting products greater than K# using filter() function res = list(filter(lambda sub: prod(sub) > K, test_list))# printing resultprint("Tuples with product greater than K : " + str(res)) |
The original list is : [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)] Tuples with product greater than K : [(4, 5, 7), (8, 4, 2)]
Time complexity: O(n*m), where n is the length of the input list and m is the maximum length of the tuples in the list.
Auxiliary space: O(k), where k is the number of tuples in the input list that have a product greater than K.
Method #3: Using math.prod() method
Python3
# Python3 code to demonstrate working of# Filter Tuples Product greater than Kimport math# initializing listtest_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 50res = [sub for sub in test_list if math.prod(sub) > K]# printing resultprint("Tuples with product greater than K : " + str(res)) |
Output:
The original list is : [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)] Tuples with product greater than K : [(4, 5, 7), (8, 4, 2)]
Time complexity: O(n), where n is the number of tuples in the test_list.
Auxiliary space: O(1), as the only additional space used is for the variable K and the result list, which is proportional to the number of qualifying tuples in the list.
Method#3: Using Recursive method.
Python3
# Python3 code to demonstrate working of# Filter Tuples Product greater than K#using recursive methoddef product_greaterthanK(lst,K,newlst=[],start=0): if start==len(lst): return newlst product=1 for i in lst[start]: product*=i if product>K: newlst.append(lst[start]) return product_greaterthanK(lst,K,newlst,start+1)import math# initializing listtest_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 50res = product_greaterthanK(test_list,K)# printing resultprint("Tuples with product greater than K : " + str(res))#this code contributed by tvsk |
The original list is : [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)] Tuples with product greater than K : [(4, 5, 7), (8, 4, 2)]
Time Complexity: O(n*m), Where n is number of tuples in test_list and m is number of elements in each tuple.
Auxiliary Space: O(n)
Method #4: Using a for loop
This approach uses a for loop to iterate over each tuple in the list and check if its product is greater than K. If yes, it adds the tuple to the result list. The prod() function is used to calculate the product of each tuple. Overall, this method has a time complexity of O(n*k) and an auxiliary space usage of O(m), where n is the number of tuples in the list, k is the length of each tuple, and m is the number of tuples with product greater than K.
Python3
# Python3 code to demonstrate working of# Filter Tuples Product greater than K# Using a for loop# getting productdef prod(box): res = 1 for ele in box: res *= ele return res# initializing listtest_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)]# initializing KK = 50# initializing result listres = []# iterate over each tuple in the listfor sub in test_list: # check if product of the tuple is greater than K if prod(sub) > K: # if yes, add the tuple to the result list res.append(sub)# printing resultprint("Tuples with product greater than K : " + str(res)) |
Tuples with product greater than K : [(4, 5, 7), (8, 4, 2)]
Time complexity: O(n*k), where n is the number of tuples in the list and k is the length of each tuple. The prod() function has to iterate over each element of the tuple to calculate the product, and this operation is performed for each tuple in the list.
Auxiliary space: O(m), where m is the number of tuples with product greater than K. We initialize an empty list to store the tuples that satisfy the condition, and this list can potentially grow to a size of n if all tuples satisfy the condition.
Method #5: Using filter and generator function
Here’s a new approach using a generator function that avoids computing the products of all tuples and stops evaluating the product of each tuple as soon as it exceeds K. This can save time if the tuples are large or the product quickly exceeds K for many tuples. The filter() function applies the greater_than_K_product() function to each tuple in the input list, yielding only the tuples that satisfy the condition. The resulting generator is converted to a list using the list() function to obtain the final filtered list.
Python3
def filter_tuples(lst, K): def greater_than_K_product(t): p = 1 for x in t: p *= x if p > K: return True return False return filter(greater_than_K_product, lst)# example usage:test_list = [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)]K = 50print("The original list is: ", test_list)print("Tuples with product greater than K:", list(filter_tuples(test_list, K))) |
The original list is: [(4, 5, 7), (1, 2, 3), (8, 4, 2), (2, 3, 4)] Tuples with product greater than K: [(4, 5, 7), (8, 4, 2)]
Time complexity: O(n*m), where n is the number of tuples in the list and m is the number of elements in each tuple in the worst case. However, the actual time complexity depends on how early the product of each tuple exceeds K, which can vary for different inputs.
Auxiliary Space: O(1), as the generator function and the filtered list are generated on-the-fly and do not require extra memory proportional to the size of the input.
