Form the Largest Number

Last Updated on March 28, 2022 by Ria Pathak

Concepts Used

Strings, Sorting

Difficulty Level

Hard

Problem Statement (Simplified):

Given an array of numbers, arrange them in such a way that they form the largest number on joining.

See original problem statement here

Test Case

Input:
4
64 646 56 46

Output:
646645646

Explanation:
On joining above elements in different order and combinations, we get total 24 numbers :

646465646
646645646
566464646
645664646
646566446
566466446
566464664
646564664
465664664
564664664
646465664
466465664
466456646
644656646
564664646
465664646
645646646
566446646
646644656
646464656
466466456
646466456
644664656
466464656

In all combinations, we can see 646645646 is the largest number, so 646645646 is our answer.

Solving Approach :

Bruteforce Approach:

1) We can check all the permutations of all the elements in the array.
2) For all the permutation, we’ll convert them into numbers and then check which of them is maximum and after checking all permutations we print the maximum number.
3) All permutations of the array take O(N!) which is very inefficient. So we move to another approach which is more efficient than this.

Efficient Approach :

1) The efficient approach uses String comparison and sorting.
2) We sort the array by using a custom comparing function.
3) When comparing two strings, let’s say A and B, we concatenate them in the form of AB and BA.
4) Then we check which one of them is big, if BA is greater than AB, then we swap both and move forward.
5) After sorting is done, we print all the numbers in sequence. This results in the required number.

Example

Let’s take test case we discussed above, where array a is [64,646,56,46].
We can dry run for above procedure as :

For i = 0:

• j = 1 :
  

  Value at a[i] is 64 and value at a[j] is 646.
  On cocatenating them, we get AB = 64646 and BA = 64664.
  As we can see value of BA is greater than value of AB, so we swap both values, and array becomes [646,64,56,46].

• j = 2 :
  

  Value at a[i] is 646 and value at a[j] is 56.
  On cocatenating them, we get AB = 64656 and BA = 56646.
  As we can see value of BA is smaller than value of AB, so we keep the array same.

• j = 3 :
  

  Value at a[i] is 646 and value at a[j] is 46.
  On cocatenating them, we get AB = 64646 and BA = 46646.
  As we can see value of BA is smaller than value of AB, so we keep the array same.

  For i = 1:

• j = 2 :
  

  Value at a[i] is 64 and value at a[j] is 56.
  On cocatenating them, we get AB = 6456 and BA = 5664.
  As we can see value of BA is smaller than value of AB, so we keep the array same.

• j = 3 :
  

  Value at a[i] is 64 and value at a[j] is 46.
  On cocatenating them, we get AB = 6446 and BA = 4664.
  As we can see value of BA is smaller than value of AB, so we keep the array same.

  For i = 2:

• j = 3 :
  

  Value at a[i] is 56 and value at a[j] is 46.
  As we can see value of BA is smaller than value of AB, so we keep the array same.

As we can see whole array is sorted accordigly as we wanted, so final array is [646,64,56,46]. So, we print whole array with no gap as our answer. 646645646 is our answer.

Solutions

#include <stdio.h>
#include<string.h>

void swap( char *first, char *second){

  char AB[10000], BA[10000];
  strcpy(AB, first);
  strcpy(BA, second);

  strcat(AB,second);
  strcat(BA,first);

  if(strcmp(BA,AB)>0){
    char temp[10000];
    strcpy(temp,second);
    strcpy(second,first);
    strcpy(first,temp);
  }

}

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    int n;
    scanf("%d", &n);

    char a[n][10000];
    for(int i=0; i<n; i++){
      scanf("%s", a[i]);
    }

    for(int i=0; i<n; i++)
      for(int j=i+1; j<n; j++)
        swap(a[i],a[j]);

    for(int i=0; i<n; i++)
      printf("%s",a[i]);

    printf("\n");
  }
}

#include <bits/stdc++.h>
    using namespace std;
    int myCompare(string A, string B) 
    { 
        string AB = A.append(B); 
        string BA = B.append(A); 
        return AB.compare(BA) > 0 ? 1: 0; 
    }

    int main()
    {
      int t;
      cin>>t;
      while(t--)
      {
        int n;
        cin>>n;
        vector<string> arr(n);
        for(int i=0;i<n;i++)
        {
          cin >> arr[i];
        }
        sort(arr.begin(), arr.end(), myCompare); 
        for (int i=0; i < arr.size() ; i++ ) 
            cout << arr[i];
        cout<<"\n";
      }
    }

import java.util.*; 

    class prepBytes { 

        static void printLargestVal(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 sc= new Scanner(System.in);
            int test_cases;
            test_cases = sc.nextInt();

            while(test_cases != 0){

              int n;
              n = sc.nextInt();
              Vector<String> arr; 
              arr = new Vector<>();

              for(int i=0; i<n ; i++){
                  int temp = sc.nextInt();
                  arr.add(Integer.toString(temp));
              }
              printLargestVal(arr);

              test_cases--;
            } 
        } 
    } 

for _ in range(int(input())):
	
	n = int(input())
	arr = input().split()
	arr.sort(reverse = True)
	print(*arr, sep = "")

[forminator_quiz id="1273"]

This article tried to discuss Strings, Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Strings, Sorting you can check out MYCODE | Competitive Programming.