Sort digits in Python

Question

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

• Graham: 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.
• Logikable: Suggest specifying this is Python 2... the implementation breaks in Python 3 because /= is not a floor divide.

Answer 1

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

• janos: 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.

Answer 2

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.