Given an array of numbers. Calculate a permutation when the concatenated number is the smallest. For instance, [55, 31, 312, 33] is 312313355.


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

//special lexical comparison
//In normal lexical comparison if one string is prefix of another, large string is greater than small string
//But here we have to compare last character of large string with the initial character of prefix

static int speciallexcmp(const void *a, const void *b)
{
if(*(int *)a == *(int *)b)
return 0;

char astr[16];
char bstr[16];

const char *aend = astr + snprintf(astr, 16, "%d" , *(int *)a);
const char *bend = bstr + snprintf(bstr, 16, "%d" , *(int *)b);

const char *p1 = astr, *p2 = bstr;

while(p1 < aend && p2 < bend && *p1 == *p2) //iterate while all characters are equal
{
p1++, p2++;
    }
if(p1 < aend && p2 < bend)
return *p1 - *p2;

//If one number is prefix of another number compare last charater with initial character of the prefix
if(p1 < aend) //second number is prefix of first number
{
return ( *(aend - 1) - *bstr );
}
if(p2 < bend) //first number is prefix of second number
{
return ( *(bend - 1) - *astr);
}
}

int main()
{
int a[] = {55, 31, 312, 33};
qsort(a, 4, sizeof(int), speciallexcmp);

int i;

for(i = 0; i<4; i++)
{
printf("%d",a[i]);
}

printf("\n");
}
Advertisements

3 thoughts on “Given an array of numbers. Calculate a permutation when the concatenated number is the smallest. For instance, [55, 31, 312, 33] is 312313355.

  1. Hi there,There's one little problem to your code – if(c1) { if(c1 < *bstr) return -1; return 1;}you cannot handle 31 and 3131312, for example. In that case, the output should be 3131312-31, but your code would generate a larger result: 31-3131312

  2. There is glitch in your code, as you are comparing the last digit with the first one in case of one string is prefix of other. But you should compare the firs digit of prefix one with the very first after the prefix in second one.Your code needs improvement like: //If one number is prefix of another number compare last charater with initial character of the prefix if(p1 < aend) //second number is prefix of first number { return ( *p1 – *bstr ); } if(p2 < bend) //first number is prefix of second number { return ( *astr – *p2); }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s