Python program to print sorted number formed by merging all elements in array

0 0 2 minutes read

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 4566789

Input: 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 number
 
def 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 array
 
 
def 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 code
lis = [7, 845, 69,  60]
 
# passing list to merge array function to merge
# the elements
mergeArray(lis)

Output

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 number
 
lis = [7, 845, 69, 60]
p = []
 
for i in lis:
    x = list(str(i))
    p.extend(x)
p.sort()
p = "".join(p)
print(int(p))

Output

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 sort
def 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 Code
arr = [7, 845, 69, 60]
 
result = merge_sort(arr)
 
print(result)

Output

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.