# Cranium 2013 'The lost number'

I tested my code fr several inputs like
592 593 0 59 592 7
n I’m getting right answer fr these…can someone who solved the problem tell me wt’s wrong with my code ? ?

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

bool myfun(string x, string y)
{
for(int i=0;i<x.length()&&i<y.length();i++)
{
if(x[i]==y[i])
continue;
else
return(x[i]>y[i]);
}
if(x.length()<y.length())
return(1);
else
return(0);
}

int main()
{
int T,N;
string s[100];
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(int i=0;i<N;i++)
{
cin>>s[i];
//cout<<"s[i]"<<s[i]<<endl;
}
sort(s,s+N,myfun);
//sort(v.begin(),v.end(),std::greater<long long int>());
for(int i=0;i<N;i++)
cout<<s[i];
printf("\n");
}
return 0;
}``````

did you try cases like:

2 & 21 (ans= 221)
56 & 561 (ans=56561)

1 Like

The correct solution is to sort strings using comparator

``````bool cmp(string a, string b) {
return a+b > b+a;
}
``````

Here `a+b` is the concatenation of strings. The intuitive proof: if we put numbers in some order and `a` and `b` some two consecutive strings in the list then if `a+b < b+a` it is advantageous to swap them. Indeed, if we swap them we exactly change substring `a+b` by `b+a` in the result.

But to get a complete proof one should prove that `cmp` is indeed the correct ordering. In particular one should prove transitivity property:

``````If a+b > b+a and b+c > c+b then a+c > c+a
``````

Several years ago I spent several hours for this and wrote several pages of calculations to prove this

As @vidhant noted the trickiest cases are when some strings are prefixes of other strings.

It is possible to create even trickier test:

``````3 31 314
``````

The optimal answer is 331431. So we take the shortest string then the largest and then the middle one.

5 Likes

@Vidhant yes I did !

n I gt my missing case in a lecture today
56 569 should be 56956 n 56569…so I had to compare larger string’s next digit with the short one’s 1st digit…missed that one…

@anton_lunyov thnxxx that’s probably the best solution…

Some test cases for the problem and their correct answers. You can check your answers against these.

``````8
2
5555 55557
2
3649908 364990
2
875897986678 875897986678333
3
67793 6779388111 6779323999
2
5555 555555555599
2
5555 555555555512
3
7866456786645612 7866456 786645679
3
4348 434843 48

555575555
3649908364990
875897986678875897986678333
6779388111677936779323999
5555555555995555
5555555555555512
78664567978664567866456786645612
484348434843``````

// Hi try this code…
#include
#include
#include
#include
using namespace std;
int mycompare(string x, string y)
{
string xy = x.append(y);
string yx = y.append(x);
return xy.compare(yx) > 0 ? 1 : 0;
}
int main()
{
int t,n,num,i;
string s;
cin>>t;
while(t–)
{
cin>>n;
vector myvector;
for(i=0;i<n;i++)
{
cin>>num;
ostringstream convert;
convert<<num;
s=convert.str();
myvector.push_back(s);
}
sort(myvector.begin(),myvector.end(),mycompare);
for(i=0;i<n;i++)
cout<<myvector[i];
cout<<endl;
}
return 0;
}

1 Like
//