Problem: Largest Number formed from an Array

Given a list of non negative integers, arrange them in such a manner that they form the largest number possible.

The result is going to be very large, hence return the result in the form of a string.

Input:

The first line of input consists number of the test cases. The description of T test cases is as follows:

The first line of each test case contains the size of the array, and the second line has the elements of the array.
Output:

In each separate line print the largest number formed by arranging the elements of the array in the form of a string.
Constraints:

1 ≤ T ≤ 70
1 ≤ N ≤ 100
0 ≤ A[i] ≤ 1000
Example:

Input:

2
5
3 30 34 5 9
4
54 546 548 60

Output:

9534330
6054854654

 

My idea:

This is a sorting-array (descending order) problem, you just know how to sort the array.
Here’s how I do it.
Consider every element in the list (or array) is a string, if two adjacent elements:
1. Compare the two first characters (by their ascii value, see the code to know more)
2. If the first two are equal, you will concatenate them into two string. For example, we got an array L, L[i] is an element at index i in array L, likewise, L[j] is an element  at index j.

s1 = L[i] + L[j] #string concatenation
s2 = L[j] + L[i] #string concatenation

if s1 < s2, we know that s2 is greater than s1, so we swap them Here is the full implementation in Python 2.7:

def sort(l):
    """
        sort the array (or list) l in
        special descending order
    """
    length = len(l)
    for i in range(length):
        for j in range(i+1, length):
            if l[j][0] > l[i][0]: #1
                l[j], l[i] = l[i], l[j]
            elif l[j][0] == l[i][0]: #2
                temp1 = int(''.join((l[i],l[j])))
                temp2 = int(''.join((l[j],l[i])))
                if temp1 < temp2:
                    l[j], l[i] = l[i], l[j]

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        (n), l = (input()), raw_input().split()
        sort(l)
        print ''.join(l)

 

Advertisements