Problem
Given an array of positive integers, find the max no that can be formed by any permutation of the arrangement.
input {21,9,23}, output = 92321
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the max no that can be formed by any permutation of the arrangement
Created Date : 28-Jun-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
string GenerateLargestNum(int* arr, int len )
{
vector<string> vec;
char buffer[256];
for(int i = 0; i < len; ++i){
itoa(arr[i], buffer, 10);
vec.push_back(buffer);
}
sort(vec.begin(), vec.end(), [](string str1, string str2)->bool
{
int len = str1.size() > str2.size() ? str2.size() : str1.size();
int i = 0;
while(i < len - 1 && str1[i] == str2[i]) i++;
if(i < len) return (str1[i] > str2[i]);
return (i == str1.size());
});
string ret;
for(auto it = vec.begin(); it != vec.end(); ++it) ret += *it;
return ret;
}
int main(int argc, char* argv[])
{
int arr[22] = {21, 9, 23, 91, 99};
cout << "The array is " << endl;
copy(arr, arr + 5, ostream_iterator<int>(cout, " "));
cout << endl;
cout << GenerateLargestNum(arr, 5) << endl;
for(int i = 0; i < 20; ++i){
for(int j = 0; j < 21; ++j){
arr[j] = rand() % 100;
}
cout << "The array is " << i << endl;
copy(arr, arr + i, ostream_iterator<int>(cout, " "));
cout << endl;
cout << GenerateLargestNum(arr, i) << endl;
cout << "----------------" << endl;
}
return 0;
}
Output
The array is
21 9 23 91 99
999912321
The array is 0
----------------
The array is 1
4
4
----------------
The array is 2
22 33
3322
----------------
The array is 3
42 88 6
88642
----------------
The array is 4
56 40 66 76
76665640
----------------
The array is 5
30 77 6 73 86
867773630
----------------
The array is 6
55 74 31 52 50 50
745552505031
----------------
The array is 7
58 21 88 22 46 6 30
8865846302221
----------------
The array is 8
2 50 91 36 74 20 96 21
969174503622120
----------------
The array is 9
67 28 93 48 83 7 21 10 17
93837674828211710
----------------
The array is 10
24 8 44 9 89 2 95 85 93 43
99593889854443242
----------------
The array is 11
81 89 98 9 57 72 22 38 92 38 79
989928981797257383822
----------------
The array is 12
72 55 28 46 62 86 75 33 69 42 44 16
867572696255464442332816
----------------
The array is 13
89 75 12 0 10 3 69 61 88 1 89 55 23
89898875696155323121010
----------------
The array is 14
32 32 69 54 21 89 76 29 68 92 25 55 34 49
9289766968555449343232292521
----------------
The array is 15
23 79 96 87 29 49 37 66 49 93 95 97 16 86 5
97969593878679665494937292316
----------------
The array is 16
16 71 86 63 13 55 85 53 12 8 32 45 13 56 21 58
8685871635856555345322116131312
----------------
The array is 17
22 29 61 35 50 73 66 44 59 92 39 53 24 54 10 45 49
9273666159545350494544393529242210
----------------
The array is 18
68 18 87 5 58 91 2 25 77 14 14 24 34 74 72 59 33 70
9187777472706855958343322524181414
----------------
The array is 19
77 73 70 63 68 92 85 2 80 13 27 2 99 27 25 43 24 23 72
999285807773727068634322722725242313
----------------
Press any key to continue . . .