Find max number you can create from an array of numbers

Question

Was asked this in an interview yesterday:

You are given an array of numbers (not digits, but numbers: e.g. 9, 23, 184, 102, etc.) - you need to construct the largest number from it. For example: you get 21, 2, 10 - the largest number is 22110.

This is my solution, I wonder if you can improve this?

def maximum_number(a):
    work_dict = {
        0: 0,
        1: 0,
        2: 0,
        3: 0,
        4: 0,
        5: 0,
        6: 0,
        7: 0,
        8: 0,
        9: 0
    }

    for ai in a:
        # if ai is a single digit number, just add it
        if ai in work_dict:
            work_dict[ai] += 1
            continue

        # otherwise, decompose it to it's digits
        while ai > 0:
            number = ai % 10
            work_dict[number] = work_dict[number] + 1
            ai = int(ai/10)

    max_num = int('9'*work_dict[9] + '8'*work_dict[8] + '7'*work_dict[7] + '6'*work_dict[6] +
                    '5'*work_dict[5] + '4'*work_dict[4] + '3'*work_dict[3] + '2'*work_dict[2] +
                    '1'* work_dict[1] + '0'*work_dict[0])

    return max_num

Answer 1

First of all, whenever you see this ... this is a big no-no:

'9'*work_dict[9] + '8'*work_dict[8] + '7'*work_dict[7] +
'6'*work_dict[6] + '5'*work_dict[5] + '4'*work_dict[4] +
'3'*work_dict[3] + '2'*work_dict[2] + '1'* work_dict[1] +
'0'*work_dict[0]

it could be replaced by a simple

''.join(str(i) * work_dict[i] for i in reversed(range(10)))

Of course, the initialization of the work_dict is similar. And in fact, you don't need to initialize it if you take care to use dict.get instead of dict[]:

work_dict[number] = work_dict[number] + 1
# is equivalent to
work_dict[number] = work_dict.get(number, 0) + 1  # default to 0 if not in dict

Ps., whenever you are counting something, consider using collections.Counter.

---

Warning: The rest of this answer tries to address the problem that OP say they are solving in the comments to the question. However, it is not certain that the understanding of the problem by the OP is correct. From here on, we assume that you are allowed to shuffle all the input digits, whereas the original problem probably only allows shuffling around the numbers.

---

If you want to have it as compact and "functional" as possible, it would be much easier to just sort the entire input and output it:

def maximum_number(lst):
    return int(''.join(sorted(''.join(str(x) for x in lst), reverse=True)))

However, note that this doesn't work on the empty list (which might be okay, depending on the specification of the function).

It should also be mentioned that

1. it is harder to write than the "manual loop" variant, which can be important in an interview
2. it might be harder to read and thus to debug, but I believe that this is up to the eye of the beholder to determine

---

For complexity, this is O(n log n) whereas the optimal algorithm has running time O(n). We again see the trade-off between running time and readability.

Here is an O(n) algorithm using Counter:

from collections import Counter
def maximum_number(lst):
    counter = Counter()
    for elt in lst:
        counter += Counter(str(elt))
    return int("".join(str(i) * counter[str(i)] for i in range(9, -1, -1)))

Answer 2

Your code

Your code as such seems to be functional, but not really elegant or concise.

First, the variable names don't speak for themselves. Nobody would be hurt if the function input was named numbers instead of a and number instead of ai. work_dict is also not a particularly good name since it's very generic. How about digit_histogram?

Handling single digit numbers separately seems unnecessary. The algorithm you implemented can handle them without special treatment.

When constructing max_num, there is a lot of repeated code. You could simplify this using a list comprehension and join (more on that soon).

How I would have tackled this

Since we have the luxury that combination of these numbers should be maximized in base 10, we can get their digits simply by looking at their str representation (which coincidentally happens to be in base 10 ;-) )¹.

If you include the other recommendations from above you end up with:

def maximum_number_str(arr):
    digit_histogram = {
        "0": 0, "1": 0, "2": 0, "3": 0, "4": 0,
        "5": 0, "6": 0, "7": 0, "8": 0, "9": 0
    }
    # or: digit_histogram = {str(i): 0 for i in range(10)}

    for number in arr:
        for digit in str(number):
            digit_histogram[digit] += 1

    max_num = "".join(str(i)*digit_histogram[str(i)] for i in reversed(range(10)))

    return int(max_num)

Depending on how familiar you are with Python and if other modules are allowed, you could come up with a solution using collections.Counter, or at least skip the dict initialization all-together if you use .get(...) instead of [...] when accessing the dictionary as presented by Pål GD in is answer.

Just for reference, this is how it could look like using a Counter:

from collections import Counter

def maximum_number_counter(arr):
    digit_histogram = Counter()

    for number in arr:
        digit_histogram.update(str(number))

    max_num = "".join(
        str(i) * digit_histogram[str(i)] for i in reversed(range(10)))

    return int(max_num)

---

Edit: The other way to think about that task

There seems to be a vivid discussion here if you understood the task correctly. If you follow the arguments that speak against your and my former interpretation, this actually leads to another interesting problem.

I came up with the solution below, though I highly doubt that I could have come up with this in an interview situation.

from functools import cmp_to_key


def maximize_joint_number(number1, number2):
    joined12 = int(str(number1)+str(number2))
    joined21 = int(str(number2)+str(number1))
    return joined21 - joined12


def maximum_number(numbers):
    """
    Generate the largest possible number that can be generated rearanging the
    *numbers*, not the digits of the input sequence
    """
    return int("".join(str(i) for i in sorted(numbers, key=cmp_to_key(maximize_joint_number))))

The idea to this is actually from this blog post that was given in a comment by Eric Duminil. The cmp_to_key trickery is needed because the cmp keyword was removed from sort in Python 3. You could also use cmp_to_key as a decorator, which makes it a little bit nicer:

from functools import cmp_to_key

@cmp_to_key
def maximize_joint_number(number1, number2):
    ...

def maximum_number(numbers):
    return int("".join(str(i) for i in sorted(numbers, key=maximize_joint_number)))

A quick test seems to fulfill all the presented example outputs:

if __name__ == "__main__":
    assert maximum_number([0, 12]) == 120
    assert maximum_number([2, 21, 10]) == 22110
    assert maximum_number([9, 2, 5, 51]) == 95512
    assert maximum_number([20, 210, 32]) == 3221020
    assert maximum_number([1, 19, 93, 44, 2885, 83, 379, 3928]) == 93834439283792885191

The second and third test case break implementations that would try to use something like sorted(numbers, key=str, reverse=True) (lexicographical sort) directly.

---

¹ Thanks to Peter Cordes for pointing out the inaccurate wording here in earlier revisions.

Answer 3

The question reads :

You are given an array of numbers (not digits, but numbers: e.g. 9, 23, 184, 102, etc.) - you need to construct the largest number from it. For example: you get 21, 2, 10 - the largest number is 22110. (Emphasis mine)

In a comment it was stated :

The task basically was to decompose the numbers into digits and then rearrange those digits to form the largest possible value that could be represented by these digits

Those two statements are very different and I'd tend to believe you either misunderstood the interview question or you didn't explain it properly. The example you gave, 22110 isn't constructed by the digits [2,2,1,1,0], but by the numbers [2,21,10]. This fits much more with how you worded your question.

With your code, getting an input of [20,210,32] would yield the result 3222100, but the actual answer should be 3221020 because of [32,210,20].

At least, this is all assuming that the requirements that you put in your questions are specifically the one you received in the interview, meaning you misunderstood the question.

Answer 4

As mentioned by @IEatBagels, it seems that you didn't understand the question. You're not allowed to split numbers into digits. You're only allowed to reorder whole numbers in order to get the maximum joined number. The output for [0, 12] should be 120, not 210!

Others answers are proud to be O(n) or O(n log n), but well, they're probably wrong.

So I'm proud to present this O(n!) solution:

from itertools import permutations

def joined_number(numbers):
    return int(''.join(str(number) for number in numbers))

max(permutations([20,210,32]), key= joined_number)
# (32, 210, 20)

max(permutations([1, 19, 93, 44, 2885, 83, 379, 3928]), key= joined_number)
# (93, 83, 44, 3928, 379, 2885, 19, 1)

The performance is horrible and it will fail for lists longer than ~10 elements, but at least you can play with it in order to understand what the real question was.

You can then try to look for the sort which could give you the correct answer.

Answer 5

EDIT: After talking to Baldrickk in the comments, I've realized that my sort by key method doesn't work for this problem. For instance, the below approach would sort [50,505040] as 50504050 instead of 50505040. I'm leaving the answer up for those who are interested.

---

This is my attempt at solving the problem assuming that the OP did indeed misinterpret the question and that the numbers can't be split up into digits. Going off of AlexV's answer I've come up with a simple sort by key solution (rather than sort by cmp). I would have posted this as a comment but I lack the reputation.

The first step is to realize that since the first digit is the most significant, the second digit the second most significant and so on, we can simply do an alphabetical sort.

def maximum_number(lst):
  return int("".join((str(n) for n in sorted(lst, key=str, reverse=True))))

So this will work for most cases.

But as AlexV pointed out in a comment, this neglects that, for instance, 5 should be sorted ahead of 51 (since 551>515), 1 ahead of 10, etc.

The key element to take note of here is that a number n that begins with a digit d should be sorted ahead of a number nk if k < d, but behind nk if k > d. If k = d, the order is arbitrary. This can be adjusted for by appending the first digit of every number onto itself, yielding the following solution.

def sorting_key(num):
  num_str = str(num)
  return num_str + num_str[0]

def maximum_number(lst):
  return int("".join((str(n) for n in sorted(lst, key=sorting_key, reverse=True))))

This passes all examples I've seen posted in other answers.

---

Thanks to Baldrickk for pointing out that the first revision of this answer would fail at [50,501]

Answer 6

Here's what I came up with. It runs in O(n) because of the for each loop, and seems to be a nice readable option to me.

numberList = [1, 19, 93, 44, 2885, 83, 379, 3928]

def largestNumber(value):
    string = ''
    for number in value:
        string = string + str(number)
    result = ''.join(sorted(string, reverse=True))
    return(int(result))


print(largestNumber(numberList))


Output: 99998888754433332211

Your solution works in the same time complexity, so they are both on the same page in that regard, but stringing the values together and using python's built in sorting function saves some space and complexity.