Smallest Rearrangement Spell

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?

Input Format

The number N

Constraint

N has at least 6 digits and at most 19.

Output Format

The new number, on a single line

Solutions

The resulting number is produced by putting the smallest non-zero 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.

frequency table