5
\$\begingroup\$

Given a string, assuming the string is numbers only, rearrange the string to that it is the greatest possible number.

Below is my solution to the problem above. I'd like feedback mainly on the algorithm, as I wrote this up very quickly. I used comprehension syntax to find the largest num, which I'm trying to use more. Any other feedback is appreciated as well.

def largest_number(string: str) -> str:
    """
    Given a string, organize the numbers such as the
    rearrangement is now the largest possible number
    """
    string = list(string)
    largest = ""
    for _ in string:
        largest_num = str(max([int(num) for num in string]))
        largest += largest_num
        string[string.index(largest_num)] = -1
    return largest

if __name__ == '__main__':

    # Test Cases #

    assert largest_number("12345") == "54321"
    assert largest_number("4689123") == "9864321"
    assert largest_number("9") == "9"
    assert largest_number("1923") == "9321"
\$\endgroup\$
  • 1
    \$\begingroup\$ Your solution runs in quadratic time \$\Theta(n^2)\$. You could do the same in linearithmic time \$\Theta(n \log n)\$ simply by sorting the digit list into descending order. \$\endgroup\$ – coderodde Oct 10 at 5:46
  • \$\begingroup\$ If this isn't reinventing-the-wheel, then "".join(sorted(string), reverse=True) is the best way to do it. \$\endgroup\$ – Gloweye Oct 10 at 6:46
7
\$\begingroup\$

This is an improvement on the answer by @coderodde. Just like they said, you can do this in \$\mathcal{O}(n)\$ time by counting how often each digit appears and then using a fixed output format. However, I would use collections.Counter from the standard library and string multiplication to achieve this goal:

from collections import Counter

def largest_number(string: str) -> str:
    counters = Counter(map(int, string))
    return "".join(str(d) * counters[d] for d in range(9, -1, -1))

Compared to sorting, as presented in the answer by @bullseye, and the original answer, this compares OK. It has a slight overhead for small strings due to the Counter object, but in the end it is faster than hardcoding character values and on the same level as sorting, but not better.

enter image description here

However, all three are vastly better than your \$\mathcal{O}(n^2)\$ algorithm (note the vastly different x limits):

enter image description here

As soon as you have three or more testcases, it might make sense to not repeat the testing code. Just put the input and expected output into a data structure (a list of tuples would do here), and iterate over it:

if __name__ == '__main__':
    test_cases = [("12345", "54321"), ("4689123", "9864321"), ("9", "9"), ("", "")]
    for string, expected in test_cases:
        output = largest_number(string)
        if output != expected:
            raise AssertionError(f"{string!r} gave back {output!r}"
                                 f" instead of {expected!r}")

For more complicated programs you might want to look at a testing framework like unittest.

\$\endgroup\$
  • 5
    \$\begingroup\$ I like the graphs, good job :) \$\endgroup\$ – bullseye Oct 10 at 7:35
4
\$\begingroup\$

Cannot comment on Python, but what comes to to the actual algorithm, you can do it in linear time \$\Theta(n)\$:

def largest_number_3(string: str) -> str:
    counters = [0 for _ in range(10)]
    string = list(string)
    for ch in string:
        counters[ord(ch) - ord('0')] += 1
    i = 0
    for num in range(9, -1, -1):
        for _ in range(counters[num]):
            string[i] = chr(num + ord('0'))
            i += 1
    return ''.join(string)

The above is just a counting sort since there is only 10 digits to distinguish.

\$\endgroup\$
  • 1
    \$\begingroup\$ For an input of size 50 ** 7 : Time1 (Your function): 29.697222855 seconds Time2 (My function): 5.580199974000003 seconds and might take a much longer for the OP's function, list comprehensions are much faster than explicit loops, your answer is an improvement of course to the OP's code however it's not the most efficient. \$\endgroup\$ – bullseye Oct 10 at 6:56
4
\$\begingroup\$
  • Confusing names: the function largest_number() has a string parameter it's generally not a good practice to name parameters by their types and their is a type hint in your code indicating what that is so you can call the parameter digits. Inside largest_num() there is string = list(string) where string is not a string(a list). This is super confusing when I'm looking at this part string[string.index(largest_num)] = -1 which I mistook for some line that should produce an error (because you can't assign values to string indexes) and then I realized that string is a list. Don't use such confusing names.
  • Adding to strings: largest += largest_num This form is inefficient, a string is immutable in Python and each time you're adding to largest a new string is created and assigned to the new value. Whenever you find a similar situation, use list comprehension and join it using the str.join() method.
  • A better approach: As 'coderodde' indicated in the comments, this is an \$O(N^2)\$ solution which can be simplified into the following by just sorting the string:

    def maximize_number(digits: str) -> str:
        """Return the maximum number that can be formed using the digits."""
        return ''.join(sorted(digits, reverse=True))
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.