Given the elements List, extract numbers with specific digits.
Input : test_list = [3456, 23, 128, 235, 982], dig_list = [2, 3, 5, 4]
Output : [23, 235]
Explanation : 2, 3 and 2, 3, 5 are in digit list, hence extracted elements.
Input : test_list = [3456, 23, 28, 235, 982], dig_list = [2, 3, 5, 4, 8]
Output : [23, 28, 235]
Explanation : 2, 3; 2, 8 and 2, 3, 5 are in digit list, hence extracted elements.
Method #1 : Using list comprehension + all()
In this, we check for each element in number against the elements from target list to be present, if all are found in list, element is returned.
Python3
# Python3 code to demonstrate working of# Elements with specific digits# Using list comprehension + all()# initializing listtest_list = [345, 23, 128, 235, 982]# printing original listprint("The original list is : " + str(test_list))# initializing digit listdig_list = [2, 3, 5, 4]# checking for all digits using all()res = [sub for sub in test_list if all( int(ele) in dig_list for ele in str(sub))]# printing resultprint("Extracted elements : " + str(res)) |
The original list is : [345, 23, 128, 235, 982] Extracted elements : [345, 23, 235]
Time Complexity: O(n)
Auxiliary Space: O(1)
Method #2 : Using filter() + lambda + all()
In this, filtering of elements is done using filter() + lambda, all() is used to check for all the digits from other list.
Python3
# Python3 code to demonstrate working of# Elements with specific digits# Using filter() + lambda + all()# initializing listtest_list = [345, 23, 128, 235, 982]# printing original listprint("The original list is : " + str(test_list))# initializing digit listdig_list = [2, 3, 5, 4]# filter() used to filter from logicres = list(filter(lambda sub: all( int(ele) in dig_list for ele in str(sub)), test_list))# printing resultprint("Extracted elements : " + str(res)) |
The original list is : [345, 23, 128, 235, 982] Extracted elements : [345, 23, 235]
Time Complexity: O(n), where n is the length of the input list. This is because we’re using the built-in filter() + lambda + all() function which has a time complexity of O(n) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of the input list.
Method #3 : Using Counter() + keys()+ all()
Python3
# Python3 code to demonstrate working of# Elements with specific digitsfrom collections import Counter# initializing listtest_list = [345, 23, 128, 235, 982]# printing original listprint("The original list is : " + str(test_list))# initializing digit listdig_list = [2, 3, 5, 4]freq = Counter(dig_list)# checking for all digits using all() and keys() functionres = [sub for sub in test_list if all( int(ele) in freq.keys() for ele in str(sub))]# printing resultprint("Extracted elements : " + str(res)) |
The original list is : [345, 23, 128, 235, 982] Extracted elements : [345, 23, 235]
Time Complexity: O(n) as we used hashing for searching whether the digit is present in dig_list or not
Method #4: Using itertools.filterfalse() method
Python3
# Python3 code to demonstrate working of # Elements with specific digitsimport itertools# initializing listtest_list = [345, 23, 128, 235, 982]# printing original listprint("The original list is : " + str(test_list))# initializing digit list dig_list = [2, 3, 5, 4]# filter() used to filter from logic res = list(itertools.filterfalse(lambda sub : not all(int(ele) in dig_list for ele in str(sub)), test_list))# printing result print("Extracted elements : " + str(res)) |
The original list is : [345, 23, 128, 235, 982] Extracted elements : [345, 23, 235]
Time Complexity:O(N)
Auxiliary Space:O(N)
Method #5:Using recursion
Algorithm:
- Define a function get_elements_with_specific_digits() that takes a list test_list and a digit list dig_list as input.
- Check if the input list test_list is empty. If it is, return an empty list.
- If the input list test_list is not empty, take the first element sub of the list.
- Check if all of the digits in sub are in the digit list dig_list.
- If all of the digits in sub are in dig_list, add sub to the result list and call the function recursively on the remaining elements of test_list (i.e., the elements starting from the second element).
- If not all of the digits in sub are in dig_list, call the function recursively on the remaining elements of test_list (i.e., the elements starting from the second element).
- Return the result list.
Python3
# Python3 code to demonstrate working of # Elements with specific digits# Using recursiondef get_elements_with_specific_digits(test_list, dig_list): if not test_list: return [] sub = test_list[0] if all(int(ele) in dig_list for ele in str(sub)): return [sub] + get_elements_with_specific_digits(test_list[1:], dig_list) else: return get_elements_with_specific_digits(test_list[1:], dig_list)# initializing listtest_list = [345, 23, 128, 235, 982]# printing original listprint("The original list is : " + str(test_list))# initializing digit list dig_list = [2, 3, 5, 4]# call the function to get the filtered listres = get_elements_with_specific_digits(test_list, dig_list)# printing result print("Extracted elements : " + str(res))#This code is contributed by Jyothi Pinjala. |
The original list is : [345, 23, 128, 235, 982] Extracted elements : [345, 23, 235]
Time complexity: O(n * m), where n is the length of the input list and m is the maximum length of an integer in the list (i.e., the number of digits in the largest integer). This is because we iterate through the entire list and for each integer in the list, we check if each of its digits is in the digit list.
Auxiliary space: O(n), where n is the length of the input list. This is because we create a new list to store the filtered elements.
Method 6: Use a for a loop
Approach:
- Convert the digit list into a set for O(1) lookup time.
- Initialize an empty list to store the filtered elements.
- Iterate through each element of the test_list using a for loop.
- Convert the current element to a string and convert each character to an integer using map() function.
- Check if the set of digits in the digit list is a subset of the set of digits in the current element.
- If it is, append the current element to the result list.
- Return the result list.
- Here is the code for the above approach with time and auxiliary space complexity:
Python3
def get_elements_with_specific_digits(test_list, dig_list): # Convert digit list to set dig_set = set(dig_list) # Initialize empty list for filtered elements res = [] # Iterate through each element in test_list for ele in test_list: # Convert element to string and map each character to int digits = set(map(int, str(ele))) # Check if digit set is subset of dig_set if digits.issubset(dig_set): # Append current element to result list res.append(ele) # Return filtered list return res# initializing listtest_list = [345, 23, 128, 235, 982]# printing original listprint("The original list is : " + str(test_list))# initializing digit listdig_list = [2, 3, 5, 4]# call the function to get the filtered listres = get_elements_with_specific_digits(test_list, dig_list)# printing resultprint("Extracted elements : " + str(res)) |
The original list is : [345, 23, 128, 235, 982] Extracted elements : [345, 23, 235]
Time complexity: O(n * k), where n is the length of the test_list and k is the maximum number of digits in any element of the test_list.
Auxiliary space: O(n), where n is the length of the test_list.
