3
\$\begingroup\$

Given an integer, sort the digits in ascending order and return the new integer.

  • Ignore leading zeros.

Parameters:

  • Input: num {Integer}
  • Output: {Integer}

Constraints:

  • Do not convert the integer into a string or other data type.
  • Time: O(N) where N is the number of digits.
  • Space: O(1)

Examples:

  • 8970 --> 789
  • 32445 --> 23445
  • 10101 --> 111

My code (as follows) works similar to the counting sort:

def sort_digits(n):
    digit_counts = {}
    result = 0

    while n > 0:
        digit = n % 10
        digit_counts[digit] = digit_counts.get(digit, 0) + 1
        n /= 10

    power = 0
    for i in range(10, -1, -1):
        if i in digit_counts:
            while digit_counts[i] >= 1:
                result +=  i * (10 ** (power))
                power += 1
                digit_counts[i] -= 1

    return result
\$\endgroup\$
  • 1
    \$\begingroup\$ Without qualification, the constraint Do not convert the integer into a string or other data type. doesn't make much sense. For example, in your solution, you indirectly encode n as the dict digit_counts, does that count as conversion? I suspect it means "direct" conversion, but that's still a bit silly; more realistic is just return the value as an int. \$\endgroup\$ – Graham Aug 1 '18 at 0:09
  • 1
    \$\begingroup\$ Suggest specifying this is Python 2... the implementation breaks in Python 3 because /= is not a floor divide. \$\endgroup\$ – Logikable Aug 1 '18 at 0:15
5
\$\begingroup\$

1) Use collections.Counter

from collections import Counter. Counter is a subclass of dict that helps keep tallies. This way, you don't need .get(digit, 0) or if i in digit_counts, making your code look a bit cleaner.

2) Iterate in increasing order

Right now, you need a power variable to track which position to place the next digit in. If you iterated in the opposite direction (i.e. range(10)), you could do result *= 10 in each loop.

3) Use a for loop instead of while

Whenever you are iterating and incrementing/decrementing, you have the opportunity to use a for loop. In this case, for while digit_counts[i] >= 1 you don't care about the number of iterations, so you can use the _ as a "throwaway variable".

4) Code localization

Move result = 0 down so that it's just above where it starts being used. Code localization improves readability - depending on your source, the human brain can only remember 4-7 things at once. The fewer variables your reader has to track, the better.

Final Result

from collections import Counter

def sort_digits(n):
  digit_counts = Counter()

  while n > 0:
    digit_counts[n % 10] += 1
    n /= 10

  result = 0
  for i in range(10):
    for _ in range(digit_counts[i]):
      result = 10 * result + i

  return result
\$\endgroup\$
  • 3
    \$\begingroup\$ To make the integer division clear, it would be better to write n //= 10 even in Python 2 . And that way your proposed solution will work in Python 3 too. \$\endgroup\$ – janos Aug 1 '18 at 7:00
2
\$\begingroup\$

Use a simple list to count digits

Instead of a dictionary, you can simply use a list, for example:

digit_counts = [0] * 10

while n > 0:
    digit_counts[n % 10] += 1
    n //= 10

No need for other libraries.

doctests

Doctests are an easy way to verify your solution produces the expected output to different inputs. For example:

def sort_digits(n):
    """
    >>> sort_digits(8970)
    789

    >>> sort_digits(32445)
    23445

    >>> sort_digits(10101)
    111

    """
    # ... the implementation

And then run the script with python -mdoctest script.py.

\$\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.