# 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?

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.

We've worked on this challenge in these gyms: modena  milan