Generate largest number arranging a no. of given non negative integer numbers

Problem : Generate largest number –

Given a list of non negative integers, arrange them in such a manner that they form the largest number possible. The result is going to be very large, hence return the result in the form of a string.
Input:
The first line of each test case contains the size of the array(N), and the second line has the elements of the array.
Output:
Constraints : 1 ≤ N ≤ 100   and   0 ≤ A[i] ≤ 1000
Example:

Input:	Output:
A) 3 3 327 94	A) 943327
B) 5 48 728 156 91	B) 9172848156

Solution :
Logic :

1. User entered numbers are kept stored in an array.
2. One function returns left most digit of array elements.
3. Left most digit of numbers are compared.

A) if left most digits of an array element is less than that of next element, swapping occurs,number with grater left most digit gets placed in array before the number with lesser left most digit.
B) if left most digits of an array element is grater than that of next element, both elements remain in their place as earlier.
C) if left most digit of one element is same to that of next element, two different numbers are formed by combining two elements one after another & reverse ,then these two numbers are compared .Now two array elements are sorted according to grater number formed by two elements. Suppose 5 & 578 are two number to be sorted. Two numbers formed combining these two elements are 5578 & 5785.Now 5785 is larger than 5578 .So 578 is stored in array before 5 .

4. Entered numbers are arranged in proper desired order & remain stored in array consecutively.
5. Then largest number will be printed by printing all elements of that array without any space.
Code :

#include "iostream";
using namespace std;
int dig1_max(int);
void num_max(int * , int * );
main() {
    int n, temp, * arr, a, b;
    cout << "Enter number of non-negative numbers to be arranged : ";
    cin >> n;
    arr = new int[n];
    cout << ("\nEnter the numbers to be arranged : ") & amp;
    lt; & amp;
    lt;
    endl;
    for (int k = 0; k < n; k++)
        cin >> arr[k];
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (dig1_max(arr[j]) < dig1_max(arr[j + 1])) //comparing entered numbers' left most digit
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            } //swapping done between arr[i] &amp;amp; arr[i+1]
            else if (dig1_max(arr[j]) == dig1_max(arr[j + 1])) //comparing entered numbers' left most digit
            {
                a = arr[j];
                b = arr[j + 1];
                num_max( & a, & b);
                arr[j] = a;
                arr[j + 1] = b;
            } else {}
        }
    }
    cout << "The largest number formed combining entered numbers is ";
    for (int z = 0; z < n; z++)
        cout << arr[z];
}
int dig1_max(int x) //this function returns left most digit of argument
    {
        int n = 0;
        while (x > 0) {
            n = x % 10;
            x = x / 10;
        }
        return (n);
    }
void num_max(int * m, int * n) {
    int s = 1, k, c = 0, num1, num2, p, q;
    p = * m;
    q = * n;
    k = q;
    for (; k > 0; c++) {
        k = k / 10;
    } //counting no.of digit in integer number
    for (; c > 0; c--) {
        s = s * 10;
    }
    num1 = p * s + q; //number formed combining two array elements
    k = p;
    c = 0;
    for (; k > 0; c++) {
        k = k / 10;
    } //counting no. of digit in integer number
    s = 1;
    for (; c > 0; c--) {
        s = s * 10;
    }
    num2 = q * s + p; //number formed combining two array elemnets
    if (num1 > num2) //two formed numbers get compared
    { * m = p; * n = q;
    } else { * m = q; * n = p; //swapping done between two elements of array
    }
}

click here to see running code on Ideone

Explanation :

dig1_max(int x) function returns left most digit of the number that is passed to function as argument.
num_max(int * m,int *n) function compares two numbers (those are passed as argument) and helps in arranging them in array in such a manner that combination of one number & next number in array  makes larger number than  combination of reverse . Comparison is done at first based on left most digit of two numbers,if both number have same left most digit then based on number formed by combining two array elements.

Details discussion on how code executes with example input, diagram :

Let say, entered number by user are 3,327,94.
Now array arr is like

Now, for loops in program run for i=0,j=0.
If(dig1_max(arr[j])<dig1_max(arr[j+1]))
dig1_max(3) function returns 3, dig1_max(327) function returns 3
if(dig1_max(arr[j])==dig1_max(arr[j+1]))
=>if(3=3) =>true
a=3,b=327

num_max(&a,&b)
num1=p*s+q=3*1000+327=3327
num2=q*s+p=327*10+3=3273
if(num1>num2) //condition true here

No change in array elements’ position  After execution of this function,

Now ,for loops in program run for i=0,j=1
if(dig1_max(arr[j])<dig1_max(arr[j+1])) => if(3<9)=>condition true , swaping is done between element of arr[1] & arr[2],means 327 & 94 swap their position in array.
Now, array is like

Now,for loops in program runs  for i=1,j=0.
if(dig1_max(arr[j])<dig1_max(arr[j+1]))
If(3<9)=>condition true  , Swaping between 3 & 94 occur in array

Now, array is like

Now, for loops in program run for i=1 ,j=1
if(dig1_max(arr[j])<dig1_max(arr[j+1]))
If(3<3) //condition false
else if(dig1_max(arr[j])==dig1_max(arr[j+1]))
=>if(3=3) //no change occurs in array actually.
Now, array is like

All elements of array arr are printed without any space. So it prints 943327 .This is the largest number can be formed by combination of entered numbers.

Another Code To Generate largest number :

#include "iostream";#
include "algorithm";#
include "vector";#
include "string";
using namespace std;
int num_max(string, string);
int main() {
    int n;
    string str;
    cout << "Enter number of non-negative numbers to be arranged : ";
    cin >> n;
    cout << "\nEnter the numbers to be arranged : ";
    vector < string > vec;
    for (int k = 0; k < n; k++) {
        cin >> str;
        vec.push_back(str); //inputted string gets into vector
    }
    sort(vec.begin(), vec.end(), num_max); //sorting done according to num_max() function
    cout << "\nThe largest number formed combining entered numbers is ";

    for (int I = 0; vec.size(); I++)
        cout << vec[I];
    return 0;
}
int num_max(string A, string B) //this function compares two numbers as string
    {
        string AB = A.append(B);
        string BA = B.append(A);
        if (AB.compare(BA) > 0)
            return 1;
        else
            return 0;
    }

click here to see running code on Ideone

 Explanation:

Entered numbers by user are inputted as string & stored in vector.sort function is called with 3 arguments sorting starting position by begin function, sorting position by end function, the function (num_max() function) according to which sorting will be done.Compare function compares two strings AB & BA , if 1is returned ,then AB is grater than BA, in the sort function AB will get ahead of BA.If 0 is returned ,then BA is grater than AB ,in the sort function BA will get ahead of AB .Then elements of vector will be printed in desired sorted order.