Finding the maximum concatenate number from the list of numbers provided

Question

Problem Statement :

Input Format : First line of the input contains an integer n. Second line of inputs contains the n array elements

Output format : The largest number that can be composed using all the array elements

Constraints : 1<=n<=100 and 1<=array elements<=1000

A simple sorting algorithm does not work for inputs like : 2,21 which gives the output as 212, but the largest number is 221

Hence I came up with the following algorithm :

1. Sort all the numbers in descending order with respect to their msd (most significant digit)
2. Find out ranges of elements having the same msd
3. within each range containing elements of same msd, we sort each element according to a value returned by a upgrade function. Upgrade function does not alter values of elements.

---

The upgrade function returns a value on the following basis :

if element is equal to 1000 then -1 is returned, which causes it to be placed at the end of the array

if element is single digit and is equal to the msd of its range, we return msd100 + msd10 + msd

if element is double digit and is equal to msd10 + msd, we return msd100 + msd*10 + msd

if elemment is double digit we return element*10

in other cases we return the element

---

I came up with this algorithm considering the inputs 532, 5 , 55 ,56 the maximum number should be 56,555,532

My code :

#include<stdio.h>
#include<stdlib.h>
void sort_msd(int arr[],int n);
void range_provider_msd(int arr[], int n); // finds out the indexes within which elements of same msd are present
void swap(int a,int b, int arr[]); // swaps array elements with index a and b in array arr[]
int msd(int n); //finds msd of n
void sort_final(int range_left,int range_right,int arr[], int msd_); //gives the final sort on the basis of upgrade function
int upgrade(int n,int msd_);    //upgrades element for better comparison
int main()
{

    int n; //n is number of element in array
    scanf("%d",&n);
    int*arr=(int*)malloc(n*sizeof(int));
    for(int i=0;i<n;++i){scanf("%d",&arr[i]);}

    sort_msd(arr,n); //soritng according to msd

    range_provider_msd(arr,n); 
    for(int i=0;i<n;++i){printf("%d",arr[i]);}

return 0;
}
void sort_msd(int arr[],int n)
{
    for(int i=0;i<n;++i)
    {
        int max_index=i,max_msd=msd(arr[i]);
        for(int j=i+1;j<n;j++)
        {
            int compare_msd=msd(arr[j]);
            if(compare_msd>max_msd)
            {
                max_index=j;
                max_msd=compare_msd;
            }
        }
        swap(i,max_index,arr);
    }
}
int msd(int n)
{
    while(n>=10)
    {
        n=n/10;
    }
    return n;
}
void swap(int a,int b, int arr[])
{
    int temp=arr[a];
    arr[a]=arr[b];
    arr[b]=temp;
}
void range_provider_msd(int arr[], int n)
{
    //following code finds out the index ranges for elements with same msd and passes them onto the sort_final function
    int left_range=0,right_range=0;
    for(int i=1;i<(n+1);++i) //n+1 to check for the special case for last elements being equal
    {
        if(msd(arr[left_range])-msd(arr[i]) == 0 && left_range<n-1 && i<n)
            ++right_range;
        else if(right_range== n-1 && i==n) //special code when last elements are equal
        {
            sort_final(left_range,right_range,arr,msd(arr[left_range]));
        }
        else 
        {
            sort_final(left_range,right_range,arr,msd(arr[left_range]));            
            left_range=right_range+1;
            ++right_range;
        }
    }
}

void sort_final(int range_left,int range_right,int arr[],int msd_)
{
    for(int i=range_left;i<=range_right;++i)
    {
        int max_index=i;
        for(int j=i+1; j<=range_right;++j)
        {
           if(upgrade(arr[j],msd_)>upgrade(arr[max_index],msd_))
           max_index=j; 
        }
        swap(i,max_index,arr);
    }
}

int upgrade(int n, int msd_)
{
    if(n==1000)
        return -1;
    else if(n<10 && n==msd_)
        return(100*msd_ + 10*msd_ + msd_);
    else if(n>=10 && n<100 && n==(10*msd_+msd_))
        return(100*msd_ + 10*msd_ + msd_);
    else if(n>=10 && n<100)
        return(n*10);
    else
        return(n); 
}

I submitted this code on my grading system and got stuck on 9th test out of 11 tests, and test does not specify what inputs I am getting stuck on. How can I find a case in which the program fails to output the right answer?

Or is there any easier and obvious method to solve this problem? I have no knowledge of data structures or something like that.

p.s This is one of my assignments from the Coursera course "algorithmic toolbox" by University of California San Diego.

Answer 1

How can I find a case in which the program fails to output the right answer?

Try

int n = 2;
int*arr=(int*)malloc(n*sizeof(int));
arr[0] = 56;
arr[1] = 561;

Your code will give

56156

but you could have formed

56561

So your calculation of "weight" of the individual number is wrong.

Try this code:

#include<stdio.h>
#include<stdlib.h>

// Struct to holde an input value and a calculated weight
struct d
{
    int n;
    int w;
};

// Calculate weight (note: n must be in range [1:1000])
int gw(int n)
{
    if (n < 10)
    {
        return 9*11*111*10*n + 2;
    }
    if (n < 100)
    {
        return 9*111*10*n + 1;
    }
    if (n < 1000)
    {
        return 9*11*10*n;
    }
    return 1;
}    

// qsort compare function
int cmp(const void* a, const void* b)
{
    struct d* pa = (struct d*)a;
    struct d* pb = (struct d*)b;
    
    if (pa->w > pb->w) return -1;
    if (pa->w < pb->w) return 1;
    return 0;
}

int main()
{
    // Take input into array of struct d
    int n = 4;
    struct d arr[n];    
    arr[0].n = 54;
    arr[1].n = 545;
    arr[2].n = 5;
    arr[3].n = 551;

    // Calculate weights
    for (int i=0; i<n; ++i)
    {
        arr[i].w = gw(arr[i].n);
    }
    
    // Sort the array
    qsort(arr, n, sizeof arr[0], cmp);
    
    // Print the result
    for(int i=0; i<n; ++i)
    {
        printf("%d", arr[i].n);
    }
    puts("");

    // Done
    return 0;
}

Output:

555154554

Some hints for understanding the weight calculation.

Assume N1 is a 1 digit number, N2 is a 2 digit number and N3 is a 3 digit number.

Let's say you want to select between a N2 and a N3 number (i.e. which to use first). Depending on which you use first you get two different numbers that can be compared. Doing the math will give:

1000 * N2 + N3 >= 100 * N3 + N2

rewrite to

999 * N2 >= 99 * N3

rewrite to

9 * 111 * N2 >= 9 * 11 * N3

Let's do the same for N1 and N3:

1000 * N1 + N3 >= 10 * N3 + N1

rewrite to

999 * N1 >= 9 * N3

rewrite to

9 * 111 * N1 >= 9 * N3

rewrite to

9 * 11 * 111 * N1 >= 9 * 11 * N3

Let's do the same for N1 and N2:

100 * N1 + N2 >= 10 * N2 + N1

rewrite to

99 * N1 >= 9 * N2

rewrite to

9 * 11 * N1 >= 9 * N2

rewrite to

9 * 11 * 111 * N1 >= 9 * 111 * N2

So we have 3 equations:

9 * 111 * N2 >= 9 * 11 * N3

9 * 11 * 111 * N1 >= 9 * 11 * N3

9 * 11 * 111 * N1 >= 9 * 111 * N2

Notice that the scaling for N1 is always the same (i.e. 9 * 11 * 111), the scaling for N2 is always the same (i.e. 9 * 111) and the scaling for N3 is always the same (i.e. 9 * 11).

That's the basis for the weight calculation.

Oh yes... the extra * 10 and add of 1 or 2 in the function is for handle of ties. In that case we want the number with fewest digits first.

So after assigning weight to all numbers, all you need is qsort. You don't need any "pre-sorting" based on "most significant digit".

Just calculate weight. Then sort the array. Done.

Edit

I just noticed this:

I have no knowledge of data structures or something like that.

Well, if that means you want a solution without use of struct you can move the weight calculation into the qsort compare function. Then you won't need the struct but the sorting will be slower as the weights will be calculated several times.

Anyway it would be like:

#include<stdio.h>
#include<stdlib.h>

int gw(int n)
{
    if (n < 10)
    {
        return 9*11*111*10*n + 2;
    }
    if (n < 100)
    {
        return 9*111*10*n + 1;
    }
    if (n < 1000)
    {
        return 9*11*10*n;
    }
    return 1;
}


int cmp(const void* a, const void* b)
{
    int na = *(int*)a;
    int nb = *(int*)b;
    int wa = gw(na);
    int wb = gw(nb);    
    
    if (wa > wb) return -1;
    if (wa < wb) return 1;
    return 0;
}

int main()
{
    // Take input into array of struct d
    int n = 4;
    int arr[n];    
    arr[0] = 54;
    arr[1] = 545;
    arr[2] = 5;
    arr[3] = 551;

    qsort(arr, n, sizeof arr[0], cmp);
    
    for(int i=0; i<n; ++i)
    {
        printf("%d", arr[i]);
    }
    puts("");

    return 0;
}

Answer 2

Or is there any easier and obvious method to solve this problem

If you are looking for new algorithm, check whether these codes satisfies your testcases (please modify the output method according to your requirement, in my code, at the end, I have printed the largeset possible integer to STDOUT):

C

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

char *cmp(char *n1, char *n2)
{
    char n1_n2[9] = "", n2_n1[9] = "";
    strcat(n1_n2, n1);
    strcat(n1_n2, n2);
    strcat(n2_n1, n2);
    strcat(n2_n1, n1);

    int r = strcmp(n1_n2, n2_n1);
    
    if (r < 0) return n2;
    else return n1;
}

void sort(int n, char arr_str[][5])
{
    for (int i=0; i<n; i++)
    {
        int idx = i;
        for (int j=i+1; j<n; j++)
        {
            char *r = cmp(arr_str[j], arr_str[idx]);
            if (r == arr_str[j])
            {
                idx = j;
            }
        }

        char temp[5];
        strcpy(temp, arr_str[idx]);
        strcpy(arr_str[idx], arr_str[i]);
        strcpy(arr_str[i], temp);
    }
}

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

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

    sort(n, arr_str);
    for (int i=0; i<n; i++)
    {
        printf("%s", arr_str[i]);
    }
    printf("\n");

    return 0;
}

Python

def cmp(n1, n2):
    n1_n2 = n1 + n2
    n2_n1 = n2 + n1
    return [n1, n2][n2_n1 > n1_n2]

n = int(input())
arr = list(input().split())
for i in range(n):
    index = i
    for j in range(i+1, n):
        r = cmp(arr[index], arr[j])
        if r == arr[j]:
            index = j
    temp = arr[index]
    arr[index] = arr[i]
    arr[i] = temp
result = [""]
for i in arr:
    result[0] += i
print(result[0])

Answer 3

Edit #4 - Epilogue:

1. Permutation (below) causes exponentially expensive processing.
2. "Complex data structure" (below) may be too advanced for raw beginner.
3. "On-the-fly" value conversions (below) risk exponentially increasing cost.

Because the values being processed are both small and well constrained, the following code exploits each uint32_t array element as a "poor man's" composite datatype. In a single traversal, array values are adjusted becoming amenable to the required sorting (without on-the-fly re-computations). After sorting, a second traversal restores the values for final printing. This is feasible, in this instance, owing to the nature of the problem constraints. Putting this forward as perhaps educational reading.

#include <stdio.h>
#include <stdint.h> /* uint##_t */
#include <stdlib.h> /* qsort() */

int cmp( const void *p0, const void *p1 ) {
    uint32_t x = *(uint32_t*)p0;
    uint32_t y = *(uint32_t*)p1;

    // NB: descending sort order wanted here
    return (x < y) ? 1 : (x > y) ? -1 : 0;
}

uint32_t arr[] = { 5, 5, 532, 10, 55, 56, 1000, 54, 54, 78, 9, };
const size_t n = sizeof arr/sizeof arr[0];

int main( void ) {
    size_t i;

    puts( "original sequence" );
    for( i = 0; i < n; i++ ) printf( ",%u" + !i, arr[ i ] ); puts( "" );

    // assemble easily sortable composite by calculating
    // "promoted" values from the constrained (10bit) range:
    //      1 <= x <= 1000 ==> 0x001 <= x <= 0x3E8 ... max 10bits needed

    // "promotion" of a value applies "base10 left shift" (aka "times 10")
    // and replicating value's Least Significant Digit to pad-on-the-right
    // Eg: 8 ==> 8888, 27 ==> 2777, 354 ==> 3544

    // NB: 9 or 99 or 999 are promoted to 9999 (0x270F) (max value)
    // composite requires/uses (16+2+10) 28 bits of uint32_t datatype

    // possibly "expensive" modulo calc. now performed only once per array element
    // versus recomputing for every pairing presented by qsort()
    // excluding printing, this requires two traversals of the array.

    for( i = 0; i < n; i++ ) {
        uint32_t x = arr[ i ]; // a copy for brevity
//                              +--- b9 to b0 - original 10 bit value 
//                              |        +--- b11 to b10 - 2 bits of magnitude
//                              |        |          +--- b31 to b12 - promoted value 
//                              |        |          |
             if( x <   10 ) x = x | (0x3 << 10) | ( (x * 1111         ) << 12 );
        else if( x <  100 ) x = x | (0x2 << 10) | ( (x * 100 + x%10*11) << 12 );
        else if( x < 1000 ) x = x | (0x1 << 10) | ( (x * 10 + x%10    ) << 12 );
        else                x = x | (    0    ) | ( (x                ) << 12 );
        arr[ i ] = x; // replace value with its composite
    }

    puts( "\ncomposite array values pre-sorting" );
    for( i = 0; i < n; i++ ) printf( ",%07X" + !i, arr[ i ] ); puts( "" );

    // sort array elements
    qsort( arr, n, sizeof arr[0], cmp );

    puts( "\ncomposite array values post-sorting" );
    for( i = 0; i < n; i++ ) printf( ",%07X" + !i, arr[ i ] ); puts( "" );

    // restore values to only the original value
    for( i = 0; i < n; i++ ) arr[ i ] &= 0x3FF; // only the low 10 bits

    puts( "\nreordered with separators" );
    for( i = 0; i < n; i++ ) printf( ",%u" + !i, arr[ i ] ); puts( "" );

    puts( "\ncompressed result" );
    for( i = 0; i < n; i++ ) printf( "%u", arr[ i ] ); puts( "" );

    return 0;
}

Result:

original sequence
5,5,532,10,55,56,1000,54,54,78,9

composite array values pre-sorting
15B3C05,15B3C05,14CA614,03E880A,15B3837,1622838,03E83E8,1544836,1544836,1ED084E,270FC09

composite array values post-sorting
270FC09,1ED084E,1622838,15B3C05,15B3C05,15B3837,1544836,1544836,14CA614,03E880A,03E83E8

reordered with separators
9,78,56,5,5,55,54,54,532,10,1000

compressed result
9785655555454532101000

---

Edit #3: Final update:
@SupportUkraine recently updated their (OP accepted) answer to provide two solutions; one version using a struct, and the other without using a compound datatype (with the inevitable cost of foreseeably lower performance.)

Below is a similar solution employing a data manipulation technique that some might find somewhat easier to understand.

The OP's code mistakenly focuses on the Most Significant Digit when, as demonstrated by debugging values down below, it is the Least Significant Digit that "levels out" values of different magnitudes for those values to be sorted into the positions that solve this task.

#include <stdio.h>
#include <stdint.h> /* uint##_t */
#include <stdlib.h> /* qsort() */

uint32_t cnvrt( uint32_t x ) { // convert value for comparison
    // EG:
    // single digit  7: ( 76 => 7666) < ( 7 => 7777) < (779 => 7799)
    // or
    // double digit 55: (520 => 5200) < (55 => 5555) < (556 => 5566)
    // or double digit resulting in duplication:
    // 10 => 1000 so: (10 => 1000) == (1000)... What to do??
    // ... tie breaker in cmp() returns original "10" vs "1000"
    // ... and considers 10 > 1000 to achieve desired DESCENDING sequencing

         if( x <   10 ) x = x * 1111;           // 4 digits.   3 ==> 3333
    else if( x <  100 ) x = x * 100 + x%10*11;  // 4 digits.  27 ==> 2777
    else if( x < 1000 ) x = x * 10 + x%10;      // 4 digits. 734 ==> 7344
//  else x = 1000; // not needed

    return x;
}

int cmp( const void *p0, const void *p1 ) {
    uint32_t xOrg = *(uint32_t*)p0, xCnv = cnvrt( xOrg );
    uint32_t yOrg = *(uint32_t*)p1, yCnv = cnvrt( yOrg );

    // NB: descending sort order wanted here
    return
        (xCnv < yCnv)
        ? 1
        : (xCnv > yCnv)
          ? -1
          : (xOrg > yOrg) // converted are equal, so original determines sort order
            ? 1
            : (xOrg < yOrg)
              ? -1
              : 0; // only 1000 vs 1000 requires this 0 ('equal') return value
}

uint32_t arr[] = { 5, 5, 532, 10, 55, 56, 1000, 54, 54, 78, };
const size_t n = sizeof arr/sizeof arr[0];

int main( void ) {
    size_t i;

    // original sequence
    for( i = 0; i < n; i++ ) printf( ",%u" + !i, arr[ i ] ); puts( "" );

    qsort( arr, n, sizeof arr[0], cmp );

    // reordered with separators to check
    for( i = 0; i < n; i++ ) printf( ",%u" + !i, arr[ i ] ); puts( "" );

    // compressed result
    for( i = 0; i < n; i++ ) printf( "%u", arr[ i ] ); puts( "" );

    return 0;
}

Credit and thanks to @SupportUkraine for pointing out a productive direction for achieving the desired outcome while doing data manipulation "on-the-fly". It would be remiss of me to not acknowledge the heavier burden imposed on the processor by the modulo calculations used in this code. On the other hand, this technique would continue to work (still using only uint32_t values) if the data range was increase from 1-to-1000 up to 1-to-100'000'000 (ie. 9 digits instead of only 4.)

Following are two older versions of this answer submitted in recent days.

---

Or is there any easier and obvious method to solve this problem ?

The OP's code demonstrates a valiant attempt to transform array values for ordering to fulfill the task. As often happens, fixating on given parameters blinds one to simpler alternatives. Sadly, trying to debug the OP's code would only contribute to venturing farther down the rabbit hole.

This problem is a case study for brute-force "permutations" seeking a "best" value.
It is a variation of "The Travelling Salesman Problem."

The "nut to be cracked" is finding/coding an algorithm to solve the problem. The gathering and verification of numeric user input is not the issue. For simplicity, the code below uses compile-time string representations of sample data. Conversion of an array of values to its equivalent as strings is left as an exercise for the reader.

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

char *elements[] = { "532", "5", "55", "56" }; // sample data
const int nElements = sizeof elements/sizeof elements[0];
int used[ nElements ]; // flags denoting availability of each element during recursion
char out[ 128 ]; // big enough to serve this example

void go( size_t k, char *p ) {
    // working copy of string, so far
    char wrk[ 128 ], *at = wrk + strlen( strcpy( wrk, p ) );

    for( size_t i = 0; i < nElements; i++ )
        if( !used[i] ) { // grab next available element
            strcpy( at, elements[ i ] ); // in turn, 'tack' each element as a suffix
            if( k+1 == nElements ) { // at the extent of recursion
                if( strcmp( wrk, out ) > 0 ) { // is this "better" (ie. "larger")?
                    strcpy( out, wrk ); // preserve as "best so far"
                //  puts( out ); // debugging showing improving results
                }
                return;
            }
            used[i] = 1; // mark this element 'used'
            go( k+1, wrk ); // next level, please
            used[i] = 0; // this element now available
        }
}

int main( void ) {
    go( 0, out );
    puts( out ); // the final result
    return 0;
}

Result with "progress debugging" enabled:

53255556 // notice each reported value is larger than the previous
53255655
53256555
55325556
55325655
55553256
55556532
55653255
55655532
56532555
56553255
56555532
56555532 // final result

The usual prohibition against using "global variables" has been ignored here for the sake of clarity. The variables could be passed to go() as (cluttering) parameters.

NB: Were there 1000 elements, each possibly 3 digits long, it's obvious this code's tiny buffers would not work. Perhaps another exercise is to judiciously allocate enough dynamic storage. Perhaps another exercise is to use just two buffers; one for the "so far" achieved result, and the other that is "cleaned up" (re-terminated) when one level of recursion is 'popped'.

EDIT:
The code above will try ALL permutations, even when a previous permutation may be, for instance, "345678..." and the current version is prefixed "345111...". Obviously, the finished result of this exploration will compare as less than what has already been achieved. Further work on this (many levels of permuting to go) will be senseless. Another exercise for the reader may be to detect this condition early and 'prune' the search of that branch of the tree.

EDIT #2:
Motivated by the (frightening) insight shared by @SimonGoater below, here's another version that won't occupy a processor with examining (worst case) 100! permutations.
(100! is 93326215 x 10¹⁵⁰ plus change. Thanks, Simon!)

"I have no knowledge of data structures or something like that."

There's no time like the present to start learning. A term related to "programming" is "data processing". In order to work with data, one must learn about data structures. The following uses a simple C struct to bind each original value in the data array to an appropriate generated value useful for sorting. (Note the use of the thoroughly tested library function qsort(). DIY sorting implementations are hard for a reader to trust.)

Note: the (magic) constant 1000. Base10 comes from the problem constraint 1 <= x <= 1000. Zero is an invalid value, as are values greater than 1000. Because of the promotion of smaller values to a value useful for sorting, care must be taken to not overflow the decimal representation provided by, in this example, an unsigned long. Eg: if the problem changed and the range maximum increased, the value 9 might be promoted to 99'999. As this is >65'535, a uint16_t datatype would overflow. Be forewarned.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h> /* qsort() */

typedef struct {
    uint32_t org; // original value
    uint32_t nrm; // 'normalised' (prefix)
} Arr;

int cmp( const void *p0, const void *p1 ) {
    Arr *px = (Arr*)p0;
    Arr *py = (Arr*)p1;

    // if normalised are equal, use original to determine if one is larger
    if( px->nrm == py->nrm )
        return px->org - py->org; // NB: descending

    return py->nrm - px->nrm; // NB: descending
}

Arr arr[] = { {5}, {5}, {532}, {10}, {55}, {56}, {1000}, {54}, {54}, {78}, };
const size_t n = sizeof arr/sizeof arr[0];

int main( void ) {
    size_t i;

    // show original sequence
    for( i = 0; i < n; i++ )
        printf( "%s%d", "," + !i, arr[ i ].org );
    puts( "" );

    // 'normalise' small values of arr[] so all are in a "prefix" range
    for( i = 0; i < n; i++ ) {
        arr[ i ].nrm = arr[ i ].org; // duplicate value here
        while( arr[i].nrm < 1000 )
            arr[i].nrm = (uint32_t)( arr[i].nrm*10 + arr[i].nrm%10 ); // reproduce low value digit

        printf( "%4d (%d)\n", arr[ i ].org, arr[ i ].nrm ); // debugging
    }

    qsort( arr, n, sizeof arr[0], cmp );

    // show reordered with separators to check
    for( i = 0; i < n; i++ )
        printf( "%s%d", "," + !i, arr[ i ].org );
    puts( "" );

    // show compressed result
    for( i = 0; i < n; i++ )
        printf( "%d", arr[ i ].org );
    puts( "" );

    return 0;
}

Result:

5,5,532,10,55,56,1000,54,54,78 // original sqnc
   5 (5555) // debugging reveal
   5 (5555)
 532 (5322)
  10 (1000)
  55 (5555)
  56 (5666)
1000 (1000)
  54 (5444)
  54 (5444)
  78 (7888)
78,56,5,5,55,54,54,532,10,1000 // reordered
785655555454532101000 // compressed

Upon reflection, the OP's intent comes into view. Kudos for the effort! Hopefully this code demonstrates another approach wherein it is not attempting to do mysterious things with values on-the-fly.