C++ Tutorial Index

C++ Tutorial C++ History C++ Installation C++ First Program C++ cin and cout C++ Data type C++ Variable C++ operator C++ Keywords

C++ Control Statements

C++ If C++ Nested if C++ If-else C++ If-else-if C++ Switch C++ Break C++ Continue C++ Goto C++ For loop C++ While loop C++ Do while loop

C++ Functions

C++ Call by Value C++ Call by Reference C++ Recursion Function C++ Inline function C++ Friend function

C++ Arrays

Single dimension array Two dimension array

C++ Strings

C++ Strings

C++ Inheritance

C++ Inheritance Single level Inheritance Multilevel Inheritance Multiple Inheritance Hierarchical Inheritance Hybrid Inheritance

C++ Polymorphism

C++ Polymorphism C++ Overloading C++ Overriding C++ Virtual Function

C++ Pointers

C++ Pointers C++ this pointer

C++ Exception Handling

C++ Exception Handling

C++ Constructors

C++ Constructors Default Constructor Parameterize Constructor Copy constructor Constructor Overloading Destructor

C++ File Handling

C++ File Handling C++ Writing to file C++ Reading file C++ Close file

Miscellaneous

C Vs C++ C++ Comments C++ Data Abstraction C++ Identifier C++ Memory Management C++ Storage Classes C++ Void Pointer C++ Array To Function C++ Expressions C++ Features C++ Interfaces C++ Encapsulation std::min in C++ External merge sort in C++ Remove duplicates from sorted array in C++ Precision of floating point numbers Using these functions floor(), ceil(), trunc(), round() and setprecision() in C++ C++ References C++ Friend Functions C++ Mutable keyword Unary Operators in C++ Initialize Array of objects with parameterized constructors in C++ Differences between #define & const in C/C++ C++ Program to Implement Shell Sort C++ Program to Implement Merge Sort Storage Classes in C Vector resize() in C++ Passing by Reference Vs. Passing by the pointer in C++ Free vs delete() in C++ goto statement in C and C++ C++ program to read string using cin.getline() C++ String Concatenation Heap Sort in C++ Swap numbers in C++ Input Iterators in C++ Fibonacci Series in C++ C ++ Program: Alphabet Triangle and Number Triangle C++ Program: Matrix Multiplication C++ Program to Print Fibonacci Triangle Stack in C++ Maps in C++ Queue in C++ C++ Bitset C++ Algorithms Priority Queue in C++ C++ Multimap C++ Deque Function Pointer in C++ Sizeof() Operators in C++ C++ array of Pointers free() Vs delete in C Timsort Implementation Using C++ CPP Templates C++ Aggregation C++ Enumeration C++ Math Functions C++ Object Class C++ Queue Initialize Vector in C++ Vector in C++ C++ STL Components Function overloading in C++ C++ Maximum Index Problem C++ find missing in the second array C++ Program to find the product array puzzle C++ Program To Find Largest Subarray With 0 Sum C++ Program To Move All Zeros To The End Of The Array C++ Program to find the element that occurs once C++ Program to find the largest number formed from an array Constructor Vs Destructor C++ Namespaces C++ OOPs Concept C++ Static C++ Structs C++ Try-Catch C++ User Defined Exceptions C++ Virtual Destructor C++ vs C# Malloc() and new in C++ Palindrome Number Program in C++ Snake Code in C++ Splitting a string in C++ Structure Vs Class in C++ Virtual Function Vs Pure Virtual Function C++ Bidirectional Iterators C++ Forward Iterators C++ Iterators C++ Output Iterators C++ Range-based For Loop Converting string into integer in C++ LCM Program in C++ Type conversion in C++ Add two numbers using the function in C++ Advantage and disadvantage friend function C++ Armstrong Number Program in C++ ATM machine program in C++ using functions Binary to Decimal in C++ Bit Manipulation in C++ C++ Constructor C++ Dijkstra Algorithm Using the Priority Queue C++ int into String C++ Signal Handling Decimal to Binary in C++ Decimal to Hexadecimal in C++ Decimal to Octal in C++ Factorial Program in C++ Function in C++ Hexadecimal to Decimal in C++ Octal to Decimal in C++ Reverse a Number in C++ Structure Vs Class in C++ C++ Forward Iterators C++ Output Iterators C++ Prime number program Char Array to String in C++ Constructor Overloading in C++ Default arguments in C++ Different Ways to Compare Strings in C++ Dynamic Binding in C++ Program to convert infix to postfix expression in C++ SET Data Structure in C++ Upcasting and Downcasting in C++ Reverse an Array in C++ Fast Input and Output in C++ Delete Operator in C++ Copy elision in C++ C++ Date and Time C++ Bitwise XOR Operator Array of sets in C++ Binary Operator Overloading in C++ Binary Search in C++ Implementing the sets without C++ STL containers Scope Resolution Operator in C++ Smart pointers in C++ Types of polymorphism in C++ Exception Handling in C++ vs Java Const Keyword in C++ Type Casting in C++ Static keyword in C++ vs Java Inheritance in C++ vs Java How to concatenate two strings in C++ Programs to Print Pyramid Patterns in C++ swap() function in C++ Structure of C++ Program Stringstream in C++ and its applications rand() and srand() in C / C++ C++ Ternary Operator C++ Scope of Variables While Loop Examples in C++ Star pattern in C++ using For Loops For Loop Examples in C++ Do-While Loop Examples in C++ Top 5 IDEs for C++ That You Should Try Once Assertions in C/C++ C++ Convert Int to String Continue in C++ While loop Diamond Pattern in C++ using For Loop How to Reverse a String in C++ using Do-While Loop How to Reverse a String in C++ using For Loop How to Reverse a String in C++ using While Loop Infinite loop in C++ Loops in C++ Returning Multiple Values from a Function using Tuple and Pair in C++ wcscpy(), wcslen(), wcscmp() Functions in C++

C++ Program to find the largest number formed from an array

Given an array, write a program to find the largest number that will be formed from the elements of the array. Arrangement should be done in such a way that all the elements contribute to make the largest number. Also, return the largest formed number in string format because the number can be very large.

For example

Test case 1

N = 5

Arr[] = {5, 9, 30, 3, 34}

Output = 9534330

Explanation

The largest value formed with the arrangement of 9,5,34,3,30.

Test case 2

N = 4

Arr[] = {60, 546, 548, 54}

Output = 6054854654

Explanation

The largest value formed with the arrangement of 60,548,546,54.

Brute-force approach

A simple approach is to sort the array and form a string in order to make a largest number. The array sorted in descending order using bubble sort does not work here.

For example, if we take 548, it is greater than 60 but after sorting 60 comes before.

Similarly, 98 is greater than 9 but after sorting it comes after.

Below is the code implementation.

Code

#include <algorithm>

#include <iostream>

#include <string>

#include <vector>

#include<bits/stdc++.h>

using namespace std;


string number(vector<int>& nums){ // declare a function

  if( nums[0]==0 && nums[nums.size()-1] == 0) // if array contains 0

return "0";

        vector<string> result;

          // push array element to string vector

        for(auto x:nums){

            result.push_back(to_string(x));

        }

          // Sort the result vector

        for(int i=0;i<nums.size()-1;i++){

            for(int j=0;j<nums.size()-i-1;j++){

                if(result[j]+result[j+1]<result[j+1]+result[j]){

                    swap(result[j],result[j+1]);

                }

            }

        }

          // Append it to ans string

        string ans="";

        for(int i=0;i<result.size();i++){

            ans+=result[i];

        }

        return ans; // print ans

}

int main()

{

          vector<int> arr;

          arr.push_back(54);

          arr.push_back(546);

          arr.push_back(548);

          arr.push_back(60);

cout  << number(arr);

          return 0;

}

Output

6054854654

Time complexity

O(n*n)

Space complexity

O(1)

Comparison based sorting

The problem occurred in the brute force approach will be covered in this approach. While sorting the array, we will modify the default compare function according to our needs.

The function my_compare() will work in this way.

This function will compare two numbers X and Y. If the formation of XY is greater then X will come first in the sorting order otherwise Y will come in the sorting order.

For example, if we have x as 541 and Y as 60. We compare 54160 and 60541. The greater one is 60541 so Y remains first.

Code

#include <algorithm>

#include <iostream>

#include <string>

#include <vector>

#include<bits/stdc++.h>

using namespace std;


int my_Compare(int X, int Y)

{

string x1= to_string(X); // x is  convert to string

    string y1 =to_string(Y); // y is  convert to string

         

          string XY = x1.append(y1); // Make combination of XY by append X to Y


          string YX = y1.append(x1); // Make combination of YX by append Y to X

     

          return XY.compare(YX) > 0 ? 1 : 0; // Compare for the greater one

}


void printLargest(vector<int> arr)

{
       

          sort(arr.begin(), arr.end(), my_Compare); // Sort the arr by using my_Compare

          for (int i = 0; i < arr.size(); i++)

                   cout << arr[i]; // Print the array arranged in form of largest number

}

int main()

{

          vector<int> arr; // make a vector

          arr.push_back(54);

          arr.push_back(546);

          arr.push_back(548);

          arr.push_back(60);

          printLargest(arr);

        return 0;

}

Output

6054854654

Time complexity

O(nlogn)

Space complexity

O(n)

Using itertools

If we want to do this problem using Python, a module itertools.combination() is used to find all the combinations of an array.

For example

Input : arr[] = [1, 2, 3, 4],

            r = 2

Output : [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Here r is the length of a set of sequences that can be formed.

Now this module can be applied to our array. We can find all the possible combinations of the array and make a string of a particular sequence set.

Finally, we will get the largest string.

Code

#import itertools from permutations

from itertools import permutations

def largest(l): # function to print largest number formed

    lst = [] #an array to store the result

    for i in permutations(l, len(l)):

        # provides all permutations of the list values,

        # store them in list to find max

        lst.append("".join(map(str,i)))

    return max(lst) # return max of the lst

print(largest([54, 546, 548, 60])) # Call largest function

Output

6054854654



ADVERTISEMENT
ADVERTISEMENT