Given a list of non-negative numbers, the task is to sort these integers according to the sum of their digits. Examples:
Input : [12, 10, 106, 31, 15] Output : [10, 12, 31, 15, 106] Input : [1111, 19, 29, 11, 12, 9] Output : [11, 12, 1111, 9, 19, 29]
Let’s discuss few Pythonic ways to do this task.
Approach #1 : List comprehension Using for loop to convert each element of list to a different list with its digits as elements. Now, use the sorted function with the above-mentioned function as key.
Python3
# Python3 Program to Sort list of# integers according to sum of digitsdef sortList(lst): digits = [int(digit) for digit in str(lst) ] return sum(digits) # Driver Codelst = [12, 10, 106, 31, 15]print(sorted(lst, key = sortList)) |
[10, 12, 31, 15, 106]
Time Complexity: O(n*logn)
Space Complexity: O(n)
Approach #2 : Using map() This approach is similar to the above approach with a slight difference that instead of for loop, we use map() to convert each element of list to a different list with its digit as elements and then follow the similar approach as above.
Python3
# Python3 Program to Sort list of# integers according to sum of digitsdef sortList(num): return sum(map(int, str(num))) # Driver Codelst = [12, 10, 106, 31, 15]result = sorted(lst, key = sortList)print(result) |
[10, 12, 31, 15, 106]
There is also a one-liner alternative to the above mentioned approach.
Python3
def sortList(lst): return sorted(lst, key = lambda x:(sum(map(int, str(x))))) |
Approach #3 Using divmod : To sort a list of numbers by the sum of their digits, you can use the divmod function to extract the digits of each number, compute the sum of the digits, and then use the sorted function to sort the list based on the sum of the digits.
Python3
def sort_by_digit_sum(lst): # Extract the digits of each number and compute the sum digit_sums = [sum(divmod(n, 10)) for n in lst] # Sort the list based on the sums of the digits return [x for _, x in sorted(zip(digit_sums, lst))]lst = [12, 10, 106, 31, 15]sorted_lst = sort_by_digit_sum(lst)print(sorted_lst) # prints [10, 12, 31, 15, 106]#This code is contributed by Edula Vinay Kumar Reddy |
[10, 12, 31, 15, 106]
This approach first uses a list comprehension to extract the digits of each number in the list and compute the sum of the digits. It then uses the sorted function to sort the list based on the sums of the digits, using the zip function to pair the sums with the corresponding numbers. Finally, it uses another list comprehension to extract the sorted numbers from the paired list.
The time complexity of the above approach is O(nlogn) because it uses the sorted function which has a time complexity of O(nlogn) for sorting the list. The space complexity is O(n) because it creates a new list with the sums of the digits of each element in the input list.
Approach #4: Using reduce()
Algorithm:
- Take input list of integers lst.
- Define a function named sortList(lst) which takes input as lst and does the following:
a. Convert the integer into a string using str() function and then iterate over the string and convert each character to an integer and append it to the list named digits.
b. Calculate the sum of the digits in the list and return the sum. - Use sorted() function to sort the list based on the key returned by sortList() function.
- Print the sorted list.
Python3
from functools import reducelst = [12, 10, 106, 31, 15]sorted_lst = sorted(lst, key=lambda x: reduce(lambda a, b: a + b, [int(d) for d in str(x)]))print(sorted_lst)#This code is contributed By Vinay Pinjala. |
[10, 12, 31, 15, 106]
Time Complexity:
The time complexity of the sortList() function is O(n), where n is the number of digits in the input integer.
The time complexity of the sorted() function is O(nlogn), where n is the length of the input list.
Space Complexity:
The space complexity of the sortList() function is O(n), where n is the number of digits in the input integer.
The space complexity of the overall program is O(n), where n is the length of the input list, as we are storing the sorted list in memory.
