Find Largest number from set of given numbers ?

  • Find number of digits in the largest number. Let us assume number of digits be n.
  • Create extended version of all numbers. In extended version, we have n+1 digit formed by concatenating the number of with itself and truncating extra digits.
  • Sorting the value from original numbers according to their extended values.
  • Concatenating to the sorted numbers produce the required result.

Sample Code in C++

/ Given an array of numbers, program to arrange the numbers to form the 
// largest number
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// A comparison function which is used by sort() in printLargest()
int myCompare(string X, string Y)
{
// first append Y at the end of X
string XY = X.append(Y);

// then append X at the end of Y
string YX = Y.append(X);

// Now see which of the two formed numbers is greater
return XY.compare(YX) > 0 ? 1: 0;
}

// The main function that prints the arrangement with the largest value.
// The function accepts a vector of strings
void printLargest(vector<string> arr)
{
sort(arr.begin(), arr.end(), myCompare);

for (int i=0; i < arr.size() ; i++ )
cout << arr[i];
}

// driver program to test above functions
int main()
{
vector<string> arr;

//output should be 5545727825
arr.push_back("25");
arr.push_back("457");
arr.push_back("278");
arr.push_back("55");
printLargest(arr);


return 0;
}

Output

5545727825

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,