See the original problem on HackerRank.
MegaBytus is a young and promising wizard who loves programming and computers.
The master GigaBytus gave him a task: crafting a spell to rearrange the digits of a number such that the number obtained is the smallest possible.
MegaBytus needs your help to find a way to verify that his spell works. Then you have to write a program that, given an integral number, will find the smallest number obtained by rearranging its digits.
Can you help him?
The number N
Constraint
N has at least 6 digits and at most 19.
The new number, on a single line
Solutions
The resulting number is produced by putting the smallest nonzero number first and then all the others, in increasing order (including duplicates).
Here is a a C++ solution based on frequency table:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

long long num; cin >> num;
int freq[10] = { 0 };
while (num)
{
freq[num % 10]++; // increment counting
num /= 10; //remove last digit
}
// first number (excluding zero)
auto firstNotZero = find_if(next(begin(freq)), end(freq), [](long long i){ return i != 0; }));
long long result = distance(begin(freq), firstNotZero);
freq[result];
for (auto i = 0; i <= 9; i++)
{
while (freq[i])
result = result * 10 + i;
}
cout << result;

A Javascript alternative by Simone Busoli:
1
2
3
4
5
6
7

function rearrange(input)
{
let zeroes = [];
const arr = input.split('').map(Number).filter(n => n ? n : (zeroes.push(0), false)).sort()
arr.splice(1, 0, ...zeroes)
console.log(arr.join(''))
}

Haskell solution by Alessandro Pezzato using
frequency table.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

countElement :: Eq a => a > [a] > Int
countElement x = (length . filter (== x))
freqTable :: Eq a => [a] > [a] > [(a, Int)]
freqTable ys xs = filter ((> 0) . snd) $ fmap (\y > (y, countElement y xs)) ys
specialSort :: [(Char, Int)] > [(Char, Int)]
specialSort (('0', zn):(y, n):fs) = (y, 1) : ('0', zn) : (y, n  1) : fs
specialSort fs = fs
srs :: String > String
srs =
(concatMap (\(y, n) > replicate n y)) .
specialSort . (freqTable ['0' .. '9'])
main = interact $ srs

Haskell solution by Alessandro Pezzato using
sort.
1
2
3
4
5
6
7

import Data.List (partition, sort)
main =
interact $
(\xs >
let (zeros, nonZeros) = (partition (== '0') . sort) xs
in head nonZeros : zeros ++ tail nonZeros)

Alternatives involve sorting with special comparison functions, left as exercises.