Given a list of numbers, the task is to find the largest number possible from the elements given in the list. This is one of the problems that is essential in competitive point of view and this article discusses various shorthands to solve this problem in Python. Let’s discuss certain ways in which this problem can be solved.
Method #1 : Using sorted() + lambda The combination of the above function can be used to perform this task. The sorted function performs the reverse sort of list indices converted into string and lambda functions handles the conversion and iteration operation.
Python
# Python code to demonstrate # largest possible number in list# using sorted() + lambdafrom functools import cmp_to_key# initializing list test_list = [23, 65, 98, 3, 4]# printing original listprint ("The original list is : " + str(test_list))# using sorted() + lambda# largest possible number in list res = sorted(test_list, key = cmp_to_key(lambda i, j: -1 if str(j) + str(i) < str(i) + str(j) else 1))# printing result print ("The largest possible number : " + ''.join(map(str,res))) |
The original list is : [23, 65, 98, 3, 4] The largest possible number : 98654323
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method #2 : Using itertools.permutation() + join() + max() The itertools.permutation can be used to get possible permutation and max function chooses the maximum of it after being converted to integer as a result of joined output as given by join function.
Python3
# Python3 code to demonstrate # largest possible number in list# using itertools.permutation() + join() + max()from itertools import permutations# initializing list test_list = [23, 65, 98, 3, 4]# printing original listprint ("The original list is : " + str(test_list))# using itertools.permutation() + join() + max()# largest possible number in list res = int(max((''.join(i) for i in permutations(str(i) for i in test_list)), key = int))# printing result print ("The largest possible number : " + str(res)) |
The original list is : [23, 65, 98, 3, 4] The largest possible number : 98654323
Method #3 : Using functools and a custom comparison function
This approach works by defining a custom comparison function that compares two numbers by concatenating them in both orders and returning the result of the comparison of the resulting integers. The sorted function is then used to sort the list using this comparison function, which results in the largest number possible being at the beginning of the list. Finally, the list is converted to a string and printed.
The cmp_to_key function is a utility function from the functools module that converts a comparison function to a key function, which can be used as the key argument in functions like sorted that expect a key function.
Python3
from functools import cmp_to_key# initializing list test_list = [23, 65, 98, 3, 4] # printing original listprint ("The original list is : " + str(test_list)) # custom comparison functiondef compare(a, b): ab = int(str(a) + str(b)) ba = int(str(b) + str(a)) if ab > ba: return -1 elif ab < ba: return 1 else: return 0 # using sorted() and custom comparison function# largest possible number in list res = sorted(test_list, key=cmp_to_key(compare)) # printing result print ("The largest possible number : " + ''.join(map(str,res)))#This code is contributed by Edula Vinay Kumar Reddy |
The original list is : [23, 65, 98, 3, 4] The largest possible number : 98654323
The time complexity of the approach using the sorted function and a custom comparison function is O(n log n), where n is the length of the list. This is because the sorted function uses a sorting algorithm that has a time complexity of O(n log n) in the average and worst case.
The space complexity is O(n), since the sorted function creates a new list as a result of the sorting operation, which has the same size as the original list.
Method #4 : Using sorted
in this, we define a custom function called compare_numbers that takes two numbers a and b as input and compares them based on their concatenated value. The function converts the numbers to strings, concatenates them in both possible orders, converts the result back to integers, and returns their difference. We then use this function as the key for the sorted function to sort the list of numbers in descending order of their concatenated value. Finally, we concatenate the sorted numbers to form the largest possible number and print it to the console.
Python3
# Original list of numbersoriginal_list = [23, 65, 98, 3, 4]# Define a custom key function to compare numbers based on their string representationdef key_func(num): return str(num)*3 # Concatenate the number with itself three times# Sort the list of numbers in descending order of their string representationsorted_list = sorted(original_list, key=key_func, reverse=True)# Concatenate the sorted numbers to form the largest possible numberlargest_number = "".join([str(num) for num in sorted_list])# Print the largest possible numberprint("The largest possible number:", largest_number) |
The largest possible number: 98654323
The complexity analysis of the code is as follows:
Defining the custom key function:
This function takes a constant amount of time, regardless of the size of the input list. Hence, its time complexity is O(1).
Sorting the original list:
Sorting takes O(nlogn) time in the worst case, where n is the size of the original list. Since we are sorting based on a custom key function, each comparison operation between the elements of the list takes O(k) time, where k is the length of the string representation of the largest number in the list. Therefore, the overall time complexity of the sorting operation in this code is O(nklogn).
Concatenating the sorted list:
Concatenating the elements of a list takes O(n) time, where n is the size of the list. In this case, we are iterating over the sorted list once, so the time complexity of concatenating the sorted list is O(n).
Therefore, the overall time complexity of the code is O(nklogn), where n is the size of the original list and k is the length of the string representation of the largest number in the list.
Method #5: using the reduce() method and lambda function:
Algorithm:
1.Initialize the list of integers.
2.Define a lambda function to compare the digits at the first index of two integers.
3.Sort the list using the lambda function as the key in the descending order.
4.Convert the sorted list of integers to a string.
5.Convert the resulting string to an integer.
Python3
from functools import reducetest_list = [23, 65, 98, 3, 4]# combining the sorted elements into a single number using reduce() and lambda functionres = int(reduce(lambda x, y: x + y, map(str, sorted(test_list, key=lambda x: int(str(x)[0]), reverse=True))))# printing original listprint("The original list is : " + str(test_list))# printing resultprint("The largest possible number is:", res)#This code is contributed by Jyothi pinjala |
The original list is : [23, 65, 98, 3, 4] The largest possible number is: 98654323
Time Complexity: O(nlogn), where n is the length of the input list. The sorting operation has a time complexity of O(nlogn).
Space Complexity: O(n), where n is the length of the input list. The space is used to store the sorted list of integers.
