find the biggest possible number comprised of the digits of of a given number

Question

Given a number N find the biggest possible number X that can be created from the given number digits.

Example: N=231 then X will be 321.

The restrictions are time complexity O(1) and space complexity O(1).

I think this has to be done with counting sort.

Answer 1

Best I can do is O(1) space and O(log(N)) time. Pretty sure it's impossible to do any better because at the bare minimum you have to analyze each digit in the input, which is log(N) right there.

The short answer is, sort the digits of N in descending order.

Pseudocode:

1. Create an array of 10 integers, all initialized to zero.
2. iterate through each digit of N. increment the slot in the array that corresponds to each digit.
3. Iterate through the array. Add N instances of the character C to the beginning of the result string, where N is the number stored in slot number C in the array.

Sample Python implementation:

N = 231
slots = [0,0,0,0,0,0,0,0,0,0]
while N > 0:
    slots[N%10] += 1
    N = int(N / 10)

result = ""
for slot_idx in range(10):
    for i in range(slots[slot_idx]):
        result = str(slot_idx) + result

print result

Result:

321