Home » Interview Questions » Array Interview Questions » Arrange given numbers to form the biggest number

Arrange given numbers to form the biggest number


()

Given an array of positive integers, this function will arrange them in such way that the arrangement will form the largest value.

Example

INPUT:
arr[] = {3, 1, 13, 34, 8}

OUTPUT:
8343131

In this method the main idea is to use library sort function. In which the function uses our comparision function.
Comparision function works in such a way that, suppose there are two numbers X and Y, then it concatenates XY and YX and takes the greater value

Example

X = 80, Y= 9.

Normal sorting will give 80, 9. But, it is false because we need the biggest number. So our function will compare 809 and 980, and gives 9, 80 as the sorted array.

Algorithm

1. Sort the array using our comparision function ie, sort(arr, arr+n, compare)

2. print the sorted array

C++ Program

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
// A comparison function which is used by sort() in largestNumber()
int Compare(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
 	if (XY > YX)
 	{
 		return 1;
 	}
 	else
 	{
 		return 0;
 	}
    
}
 
// This function prints the largest number
void largestNumber(string  arr[], int n)
{
    // Sort the numbers using library sort funtion.
    sort(arr, arr+n, Compare);
 	
 	//printing the sorted array, which is the largest number
    for (int i=0; i < n ; i++ )
        cout << arr[i];
}
 
int main()
{
    string arr[] = {"2", "1", "25", "34", "8"};
    int n = sizeof(arr)/sizeof(arr[0]);
    largestNumber(arr, n);
 
   return 0;
}

READ  4Sum

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions