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(''))
} 

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

We've worked on this challenge in these gyms: modena 
comments powered by Disqus