Python – Check if list contain particular digits

Given a List and some digits, the task is to write a python program to check if the list contains only certain digits.

Input : test_list = [435, 133, 113, 451, 134], digs = [1, 4, 5, 3]
Output : True
Explanation : All elements are made out of 1, 4, 5 or 3 only.

Input : test_list = [435, 133, 113, 451, 134], digs = [1, 4, 5]
Output : False
Explanation : 3 as a digit is required in allowed digits.

Method #1 : Using loop + str() + join()

In this, we iterate for each element in the list and check for each element to have all the digits by joining all digits, converting to string, and checking for each in all digits of elements converted to a string.

Approach:

1. Initialize a list of integers named test_list with values [435, 133, 113, 451, 134].
2. Print the original list using the print() function and string concatenation with the str() function to convert the list to a string.
3. Initialize a list of integers named digs with values [1, 4, 5, 3].
4. Convert the digs list to a string by using a list comprehension with str(ele) for each element in the digs list and then joining the resulting list using the join() function. Store the resulting string in the variable digt_str.
5. Convert the test_list list to a string by using a list comprehension with str(ele) for each element in the test_list list and then joining the resulting list using the join() function. Store the resulting string in the variable all_ele.
6. Initialize a boolean variable res to True.
7. Loop through each element in the all_ele string.
8. For each element in the all_ele string, loop through each character in the element string.
9. Check if each character is in the digt_str string. If any character is not in the digt_str string, set the res variable to False and break out of the loop.
10. After checking all characters in the element string, continue to the next element in the all_ele string.
11. After checking all elements in the all_ele string, print the result of whether all elements in the test_list are made from the required digits by using the print() function and string concatenation with the str() function to convert the res variable to a string. 

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Time Complexity: O(n^2) where n is the number of elements in the test list.
Auxiliary Space Complexity: O(n) where n is the number of elements in the test list. 

Method #2 : Using any() + list comprehension

In this, we flag off if any digit not from digit string using any() and not operation. One liner alternative extended using iteration in a list comprehension.

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Time complexity: O(n*m), where n is the length of the test_list and m is the length of the digits list. 

Auxiliary space: O(n+m), because we create two additional strings in memory to represent the test_list and digits list as strings. 

Method #3: 

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Method #4 : Using list()+map()+join()+replace()+len() methods

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Method #5: Using NumPy module

Step-by-step algorithm for implementing the approach

1. Import the NumPy library.
2. Initialize the given list test_list and required digits digs.
3. Convert test_list and digs to NumPy arrays using np.array() function.
4. Convert the test_arr to a string, join all the elements and convert it to a list of characters. Then, convert digs_arr to a list of characters.
5. Use the np.isin() function to create a boolean array representing whether each digit in each element of test_arr is in digs_arr.
6. Check if all elements of bool_arr are True using the all() function.
7. Print the result.

Output

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Time complexity: The time complexity of the approach depends on the size of the given list test_list and required digits digs. The operations involved in converting lists to NumPy arrays take constant time, i.e., O(1). Converting the test_arr to a string, joining all the elements and converting it to a list of characters takes O(n), where n is the total number of digits in the test_list. The np.isin() function takes O(m * n), where m and n are the lengths of the test_arr and digs_arr, respectively. Finally, checking if all elements of bool_arr are True using the all() function takes O(n). Therefore, the overall time complexity is O(m * n).

Auxiliary space: The auxiliary space complexity of the approach is O(n), where n is the total number of digits in the test_list. This is because we create a list of characters from the test_arr and digs_arr using the list() function, and then use the np.isin() function to create a boolean array representing whether each digit in each element of test_arr is in digs_arr. Finally, we create a boolean array of the same length as test_arr to store the result. The space required by all these data structures is proportional to the total number of digits in the test_list.

Method#6: Using Recursive method.

Algorithm:

1. Convert the digits list to a set of strings for faster membership testing using the map and set functions.
2. Define a recursive function that takes a list lst and the digits_set.
3. The base case is if the list is empty, return True as all elements are made from required digits.
4. Get the first element of the list as a string.
5. Loop through each digit in the element string and check if it’s not in the digits_set. If so, return False as the element is not made from required digits.
6. If all digits are in the digits_set, make a recursive call to the function with the rest of the list lst[1:] and digits_set.
7. Return the result of the recursive call.
8. Call the recursive function with the test_list and digs_set and store the result in res.
9. Print the original list and the result.
    

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Time Complexity:
The time complexity of this algorithm is O(n * k), where n is the number of elements in the lst and k is the maximum number of digits in an element of the lst. This is because for each element of the list, we need to loop through all its digits and check if they are in the digits_set. The worst case is when all elements have k digits.

Auxiliary Space Complexity:
The auxiliary space complexity of this algorithm is O(k), where k is the maximum number of digits in an element of the lst. This is because we need to store the digits_set for faster membership testing, and the maximum size of digits_set is k. Additionally, the recursive function has a space complexity of O(n), where n is the length of the input list lst, due to the recursion stack. However, since the maximum recursion depth is also n, the total space complexity of the algorithm is O(n + k).

Method#7:Using a regular expression:

Algorithm:

1. Create a pattern string that contains all required digits.
2. Iterate through each element in the test list.
3. Convert the element to a string and use a regular expression to match against the pattern.
4. If all elements match the pattern, set the result to True; otherwise, set it to False.
5. Output the result.

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Time complexity: O(nk), where n is the length of the test list and k is the length of the pattern string. The loop that iterates through the test list has a time complexity of O(n). The regular expression match operation has a time complexity of O(k), where k is the length of the pattern string.

Auxiliary Space: O(k), where k is the length of the pattern string. The pattern string is created based on the required digits, so its length is directly proportional to the number of required digits.

Method#8:Using filter() and set()

• Initialize the list test_list with some values.
• Initialize the value of digs with the required digits.
• Convert the digs list to a set digs_set.
• Use the filter() function to filter the elements in the test_list that contain only digits from digs_set. The filter() function takes a lambda function as an argument that checks whether the set of digits in the current element is a subset of digs_set. The lambda function converts the current element to a set of digits using set(str(x)) and checks if digs_set is a superset of that set using issuperset().
• Convert the filtered result to a list.
• Check if the filtered list is the same as the original test_list.
• Print the result.

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : False

The time complexity of the given code is O(nk), where n is the length of the input list and k is the maximum number of digits in an element of the list. The code iterates through each element of the list and each digit in the element to check if all the required digits are present. This process takes O(nk) time in the worst case, where k is the maximum number of digits in an element. The join() function used to concatenate the digits in the list and elements of the list takes O(nk) time as well.

The space complexity of the code is also O(nk), where n is the length of the input list and k is the maximum number of digits in an element of the list. The space required for the input list is O(n), while the space required for the concatenated string that contains all the elements of the list is O(nk). The space required for the digits list and the concatenated string that contains all the required digits is O(k), where k is the maximum number of digits in an element of the list. Therefore, the space complexity of the code is proportional to the size of the input list and the maximum number of digits in an element of the list.

Method#9: Using reduce():

Algorithm:

1. Construct a regular expression pattern using the required digits list
2. For each element in the given list, check if it matches the pattern
3. Combine the results of the matching operation using the reduce() function
4. Output the original list and the Boolean result indicating whether all elements match the pattern or not.

The original list is : [435, 133, 113, 451, 134]
Are all elements made from required digits? : True

Time complexity:

The time complexity of this code is O(nk), where n is the length of the given list and k is the length of the required digits list. This is because constructing the regular expression pattern takes O(k) time, and matching each element against this pattern takes O(k) time as well. Since this operation is performed on each element of the list, the total time complexity is O(nk).

Auxiliary Space:
The space complexity of this code is O(k), as the regular expression pattern is constructed using the required digits list, which takes up O(k) space. The space complexity does not depend on the length of the given list.