Problem
Find the largest number obtained by rearranging the digits in O(n) time.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the largest number obtained by rearranging the digits in O(n) time
Created Data : 28-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
int FindLargestNum(int n)
{
int digits[10] = {0};
int cnt(0);
while(n != 0){
digits[ n % 10] ++;
n /= 10;
cnt ++;
}
int retVal(0);
int index = 9;
while(cnt > 0){
while(digits[index] > 0){
retVal = retVal * 10 + index;
digits[index] --;
cnt --;
}
index --;
}
return retVal;
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 20; ++i){
int n = rand();
cout << "n : " << n;
cout << "---" << FindLargestNum(n) << endl;
}
return 0;
}
Output
n : 41---41
n : 18467---87641
n : 6334---6433
n : 26500---65200
n : 19169---99611
n : 15724---75421
n : 11478---87411
n : 29358---98532
n : 26962---96622
n : 24464---64442
n : 5705---7550
n : 28145---85421
n : 23281---83221
n : 16827---87621
n : 9961---9961
n : 491---941
n : 2995---9952
n : 11942---94211
n : 4827---8742
n : 5436---6543
Press any key to continue . . .