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 :
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.
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;
}