Given an array arr[], the task is to combine all the elements in the array sequentially and sort the digits of this number in ascending order.
Note: Ignore leading zeros.
Examples:
Input: arr =[7, 845, 69, 60]
Output: 4566789
Explanation: The number formed by combining all the elements is “78456960” after sorting the digits we get 4566789Input: arr =[8, 5603, 109, 53209]
Output: 1233556899
Explanation: The number formed by combining all the elements is “8560310953209” after sorting the digits we get “1233556899”
Approach 1:
- Convert each element of the list to a string using map() function.
- Join the list using join() function.
- Sort the string using join() and sorted()
- Convert string to an integer using type casting
- Return the result
Below is the implementation of the above approach:
Python3
# Python program to print sorted number by merging# all the elements in array function to print# sorted numberdef getSortedNumber(number): # sorting the string number = ''.join(sorted(number)) # converting string to integer number = int(number) # returning the result print(number)# function to merge elements in arraydef mergeArray(lis): # convert the elements of list to string lis = list(map(str, lis)) # converting list to string string = ''.join(lis) # passing this string to sortednumber function getSortedNumber(string)# Driver codelis = [7, 845, 69, 60]# passing list to merge array function to merge# the elementsmergeArray(lis) |
4566789
Time complexity: O(nlogn) because sorting the string in the getSortedNumber function takes O(nlogn) time, where n is the length of the string.
Auxiliary space: O(n), where n is the number of elements in the input list.
Approach 2: Using list(),str(),extend(),sort(),join() and int() methods
Python3
# Python program to print sorted number by merging# all the elements in array function to print# sorted numberlis = [7, 845, 69, 60]p = []for i in lis: x = list(str(i)) p.extend(x)p.sort()p = "".join(p)print(int(p)) |
4566789
Time complexity: O(n log n), where n is the total number of digits in the input list.
Auxiliary space: O(n), where n is the total number of digits in the input list.
Approach#3:using itertools
Algorithm
- Convert each number in the input array to a string.
- Concatenate all the strings to form a single string.
- Convert the merged string to a list of integers.
- Sort the list of integers and join them back into a single string.
- Convert the sorted string to an integer and return it.
Python3
import itertools# Function to perform the merge sortdef merge_sort(arr): # Convert each number in the # array to a string str_arr = [str(num) for num in arr] # Concatenate all the strings to # form a single string merged_str = ''.join(str_arr) # Convert the merged string to a # list of integers merged_list = [int(char) for char in merged_str] # Sort the list of integers and # join them back into a single string sorted_str = ''.join([str(num) for num in sorted(merged_list)]) # Convert the sorted string to an # integer and return it return int(sorted_str)# Driver Codearr = [7, 845, 69, 60]result = merge_sort(arr)print(result) |
4566789
Time Complexity: O(n log n), where n is the length of the input array. This is because we convert the array to a single string in O(n) time, sorting the string takes O(n log n) time, and converting the sorted string back to an integer takes O(n) time.
Space Complexity: O(n), where n is the length of the input array. This is because we need to store the merged list of integers, which has a length of n. The sorted string also has a length of n. The permutations are no longer generated and stored, so the space complexity is improved compared to the previous approach.
