Arrange given numbers to form the biggest number

Difficulty Level Easy
Frequently asked in Amazon MakeMyTrip Paytm Zoho
Array StringViews 1469

Problem Statement

Suppose you have an array of integers. The problem “Arrange given numbers to form the biggest number”  asks to rearrange the array in such a manner that the output should be the maximum value which can be made with those numbers of an array.

Example

[34, 86, 87, 765]
878676534

Explanation: We have concatenated numbers with each other such that it produces the highest value.  We have the value greatest is 765 but if we put it forward, our output will be less than the value we have got now, so we have to take 87 first and then 86 and then rest. The result should start with the rest digit.

Algorithm to Arrange given numbers to form the biggest number

1 Compare and check which value is lexicographically greater.
2. The greater value will put forward.
3. Return that value.

Explanation

We have been asked to rearrange the array in such a way that within the numbers of the array, all the numbers collectively would produce the greatest number that can be formed with the numbers of the array. So here we will be taking the inputs as a string of numbers. If the number is given we can easily convert them to strings. The question that arises is how to find the greater number when all numbers concatenated. Because the three digits number is definitely a greater number when we compare it with any two-digit number. But here we have to find the first digit of the number should be greater than any of the numbers in input. In this way, we are going to solve this problem.

We will be using a compare method for string manipulations. With this, we are manually going to sort our input lexicographically. This means if the starting digit is greater than any other number whose starting digit is lower. Then we would put it first whose starting digit is greater. Then we have to sort all of the input in this manner, now we can do this with the help of either the compare method which are predefined methods of the languages or we can traverse each and every string and find out the lexicographically greater string. But the efficient method than that is the method defined here.

Now we have to just concatenate them or simply print them as in order in which they sorted. Also, we should have taken the input in the string format, so that we can sort them in the order of lexicographical order.

Arrange given numbers to form the biggest number

Code

C++ code to arrange given numbers to form the biggest number

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int myCompare(string X, string Y)
{
    string XY = X.append(Y);
    string YX = Y.append(X);

    return XY.compare(YX) > 0 ? 1: 0;
}
void getLargest(vector<string> arr)
{
    sort(arr.begin(), arr.end(), myCompare);

    for (int i=0; i < arr.size() ; i++ )
        cout << arr[i];
}
int main()
{
    vector<string> arr;
    arr.push_back("34");
    arr.push_back("86");
    arr.push_back("87");
    arr.push_back("765");
    getLargest(arr);
    return 0;
}

878676534

Java code to arrange given numbers to form the biggest number

import java.util.Collections;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Vector;

class rearrangNumericString
{
    public static void getLargest(Vector<String> arr)
    {

        Collections.sort(arr, new Comparator<String>()
        {
            @Override
            public int compare(String X, String Y)
            {

                String XY=X + Y;

                String YX=Y + X;

                return XY.compareTo(YX) > 0 ? -1:1;
            }
        });

        Iterator it = arr.iterator();

        while(it.hasNext())
            System.out.print(it.next());

    }
    public static void main (String[] args)
    {
        Vector<String> arr = new Vector<>();
        arr.add("34");
        arr.add("86");
        arr.add("87");
        arr.add("765");
        getLargest(arr);
    }
} 

878676534

Complexity Analysis

Time Complexity

O(N*|S| log N) where “N” is the count of numbers and |S| denotes the length of the largest number. Merge sort will make N logN comparisons but since each comparison takes |S| time in the worst case. The time complexity will also be N*|S| logN.

Space Complexity

O(N*|S|) where “N” is the count of numbers. Here |S| denotes the length of the numeric input.

Translate »