Given element list, sort by factor count of each element.
Input : test_list = [12, 100, 22]
Output : [22, 12, 100]
Explanation : 3, 5, 8 factors respectively of elements.Input : test_list = [6, 11]
Output : [11, 6]
Explanation : 1, 4 factors respectively of elements.
Method #1 : Using sort() + len() + list comprehension
In this, we perform task of sorting using sort(), and len() and list comprehension is used for task of getting the count of factors.
Python3
# Python3 code to demonstrate working of # Sort by Factor count # Using sort() + len() + list comprehension def factor_count(ele): # getting factors count return len ([ele for idx in range ( 1 , ele) if ele % idx = = 0 ]) # initializing list test_list = [ 12 , 100 , 360 , 22 , 200 ] # printing original list print ( "The original list is : " + str (test_list)) # performing sort test_list.sort(key = factor_count) # printing result print ( "Sorted List : " + str (test_list)) |
Output:
The original list is : [12, 100, 360, 22, 200] Sorted List : [22, 12, 100, 200, 360]
Time Complexity: O(nlogn) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(1) additional space is not needed
Method #2 : Using lambda + sorted() + len()
In this, task of sorting is done using sorted(), and lambda function is used to feed to sorted to get factors.
Python3
# Python3 code to demonstrate working of # Sort by Factor count # Using lambda + sorted() + len() # initializing list test_list = [ 12 , 100 , 360 , 22 , 200 ] # printing original list print ( "The original list is : " + str (test_list)) # performing sort using sorted(), lambda getting factors res = sorted (test_list, key = lambda ele: len ( [ele for idx in range ( 1 , ele) if ele % idx = = 0 ])) # printing result print ( "Sorted List : " + str (res)) |
Output:
The original list is : [12, 100, 360, 22, 200] Sorted List : [22, 12, 100, 200, 360]
Method #3: Using a dictionary to store factor counts and sort by value
Algorithm:
Define an empty dictionary factor_counts.
Iterate over the elements of the input list test_list and for each element ele:
a. Define a variable count to store the number of factors of ele.
b. Iterate over the range from 1 to ele, inclusive, and increment count for each factor of ele.
c. Add a key-value pair to factor_counts with key ele and value count.
Sort test_list by factor count using the factor_counts dictionary. To do this, pass a lambda function to the sorted() function as the key parameter, which returns the value of the corresponding key-value pair in factor_counts for each element in test_list.
Return the sorted list.
Python3
# Python3 code to demonstrate working of # Sort by Factor count # Using a dictionary to store factor counts and sort by value # initializing list test_list = [ 12 , 100 , 360 , 22 , 200 ] # printing original list print ( "The original list is : " + str (test_list)) # defining an empty dictionary to store factor counts factor_counts = {} # iterating over the elements of the input list and storing factor counts in the dictionary for ele in test_list: count = 0 for idx in range ( 1 , ele + 1 ): if ele % idx = = 0 : count + = 1 factor_counts[ele] = count # sorting the list by factor count using the dictionary res = sorted (test_list, key = lambda ele: factor_counts[ele]) # printing result print ( "Sorted List : " + str (res)) |
The original list is : [12, 100, 360, 22, 200] Sorted List : [22, 12, 100, 200, 360]
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.