CODEWITHSUNDEEP
pythonlist
DaVinci
DaVinci

Reputation: 879

The largest Integer from n integers in python

The program must accept a integer and the list of integers then the output should be the largest possible integer from the given array of integers

from itertools import permutations as p
a=int(input())
print("".join(sorted(list(set(p(list(input().strip().split(" "))))))[-1]))

This is my code but it is not working since it takes too much of time to execute example Output/Input

Execution Time Limit : 500ms

Upvotes: 0

Views: 588

Answers (1)

user8408080
user8408080

Reputation: 2478

This was the first, naive approach:

As others said, sorting is the only key here. As a oneliner taking standard input:

print("".join(sorted(input().split(), reverse=True)))

This works in some test cases, but fails miserably with the case 98 987.

This is a correct approach, at least I thought so:


def compare(a, b): 
    for i,j in zip_longest(a, b): 
        if i is not None and j is not None: 
           if i<j: 
               return -1 
           elif i>j: 
               return 1 
        if i is None: 
            return int(a[0])-int(j) 
        if j is None: 
            return int(b[0])-int(i) 
    return 0

Testing

>>> a = ['24', '26', '28', '987', '556', '214', '398', '476', '542', '192', '878', '566', '744', '232', '456', '98', '2', '4', '76', '78']
>>> print("".join(reversed(sorted(a, key=functools.cmp_to_key(compare)))))
98987878787674456655654247645643982826242322214192
>>> 98987878787674456655654247645643982826242322214192 == 98987878787674456655654247645643982826242322214192
True

So it seems to work.

Explanation

zip_longest is the same as zip, but it pads for unequal lengths. Example zip_longest("1", "12") gives [("1", "1"), (None, "2")].

As long as none of the elements in the tuple are None everything is supposed to work normally:

  • If i is smaller than j, then the number containing i -- here a -- must be smaller than the number containing j -- here b -- so we return -1.
  • The other way around, it's the same.

So far, this is the same as the alphanumeric ordering. But what if one number is None? Example: Take a = 987 and b = 98. At one point, i is 7 and j is None. In alphanumeric ordering, 7 would be larger than None, a>b. But here, we have to take into account, that the numbers will be chained, so we have to in fact check, if 7 is greater than the first digit of the other number, which is 9. 7 is actually smaller, so b comes first.

If none of the conditions are met, the numbers must be equal and 0 is returned.

This worked in most test cases, but fails miserably with 98 989.

This is the correct solution:

def compare(a, b): 
    x = a+b 
    y = b+a 
    if x>y: 
        return 1 
    elif x<y: 
        return -1 
    else: 
        return 0

Testing

In [96]: a = ["98", "987"]                                                                                           
In [97]: print("".join(reversed(sorted(a, key=functools.cmp_to_key(compare)))))                                      
98987

In [98]: a = ["989", "98"]                                                                                           
In [99]: print("".join(reversed(sorted(a, key=functools.cmp_to_key(compare)))))                                      
98998

In [100]: a = ['24', '26', '28', '987', '556', '214', '398', '476', '542', '192', '878', '566', '744', '232', '456', 
     ...: '98', '2', '4', '76', '78']                                                                                
In [101]: print("".join(reversed(sorted(a, key=functools.cmp_to_key(compare)))))                                     
98987878787674456655654247645643982826242322214192

They all work

Explanation

The very first approach was too easy, the second was overcomplex. This one is the midway and actually very straight forward. Combine each pair in both possible way. Which combination yields the bigger number? That will dictate the sorting.

I hope everything is clear now and that this withstands any test case I maybe even never thought of.

Upvotes: 4

Related Questions