The largest Integer from n integers in python

Question

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

Execution Time Limit : 500ms

The text in your question does not properly describe the instructions for the task. If you want to make the biggest integer by concatenating other integers, you don't need to try every single permutation. You just need to get the highest value digits towards the start of your number. — khelwood
– khelwood, Commented May 15, 2020 at 9:06
E.g. in example 1, 60 is at the beginning of the output because it starts with a 6, highest than the others. In example 2, 92 is at the beginning of the output because it starts with a 9. — khelwood
– khelwood, Commented May 15, 2020 at 9:09

user8408080 · Accepted Answer · 2020-05-15 16:11:52Z

4

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.

edited May 15, 2020 at 16:11

answered May 15, 2020 at 9:14

user8408080

2,4781 gold badge12 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

DaVinci Over a year ago

It doesn't work for this case Input: 24 26 28 987 556 214 398 476 542 192 878 566 744 232 456 98 2 4 76 78 and the Expected O/P : 98987878787674456655654247645643982826242322214192 this code O/P:98798878787674456655654247645643982826242322142192

user8408080 Over a year ago

@Tonystark I think I have it sorted out (haha) now

mrk Over a year ago

Great job, did you check for the runtime?

user8408080 Over a year ago

For the test case mentioned above, it took 31.1 µs ± 23.3 ns per loop with print and 25.5 µs ± 60.2 ns without, on my machine. Thank you very much :D

user8408080 Over a year ago

Actually this still fails on 989 98, but I think I need a break

|

Collectives™ on Stack Overflow

The largest Integer from n integers in python

1 Answer 1

This was the first, naive approach:

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

Testing

Explanation

This is the correct solution:

Testing

Explanation

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

This was the first, naive approach:

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

Testing

Explanation

This is the correct solution:

Testing

Explanation

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related