Arrange given Numbers to Form the Biggest Number II

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple ByteDance Facebook Google MakeMyTrip Microsoft Nvidia Oracle Paytm VMware Zoho
Array String Works ApplicationsViews 3974

Problem Statement

In the “Arrange given Numbers to Form the Biggest Number II” problem, we have given an array of positive integers.  Arrange them in such a way that the arrangement will form the largest value.

Input Format

The first and only one line containing an integer n.

Second-line containing n space-separated integers.

Output Format

The first and only one line containing the final array after the arrangement.

Constraints

  • 1<=n<=10^5
  • 0<=a[i]<=10^6

Example

5
80 9
980

Explanation: 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

In this method, the main idea is to use the library sort function. In which the function uses our comparison function. The 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.

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

2. Print the sorted array

Implementation

C++ Program to Arrange given Numbers to Form the Biggest Number II

#include <bits/stdc++.h>
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 printLargest(vector<string> arr)
{
    sort(arr.begin(), arr.end(), myCompare);
    for(auto u: arr)
    {
        cout<<u;
    }
    cout<<endl;
}

int main()
{
   int n;
   cin>>n;
   vector<string> v;
   for(int i=0;i<n;i++)
   {
       string x;
       cin>>x;
       v.push_back(x);
   }
   printLargest(v);
   return 0;
}

Java Program to Arrange given Numbers to Form the Biggest Number II

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Vector;
class sum
{
    static void printLargest(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());
        System.out.println();
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        Vector<String> v = new Vector<String>();
        int n = sr.nextInt();
        for(int i=0;i<n;i++)
        {
            String x;
            x = sr.next();
            v.add(x);
        }
        printLargest(v);
    }
}
6
1 10 952 42 19 7821
95278214219110

Complexity Analysis

Time Complexity

O(n*logn) where n is the size of the given array. Here we use the concept of sorting and sorting has a running time complexity of O(nlogn) and the for loop runs in O(n) time.

Space Complexity

O(1) because we don’t use any auxiliary space here.

Translate »