One subtask was to create function to check where numbers "a" and "b" are permutations of each other...
When I finish this problem and check other solutions on forum...I found few C++ solutions. The realization of this function was awful..and extremely slow.
Here is mine:
bool is_permutation(int a,int b)
{
char test1[10]={0};
char test2[10]={0};
while(a>0 && b>0)
{
++test1[a%10];
++test2[b%10];
a/=10;b/=10;
}
if(a!=b)
return false;
return memcmp(test1,test2,10)==0?true:false;
}
There was one really close realization...
(you can ++test1[a%10];--test2[b%10]; and at the end check if test1=={0} )
But the others...
1st (O(n^2) on sorting numbers... cmon man can't you just qsort then):
#define CAP_LENGTH 8
inline int permutation(int a, int b){
static int a_digits[CAP_LENGTH];
static int b_digits[CAP_LENGTH];
static int i,j, a_length, b_length;
i=0;
do{
a_digits[i]=a%10;
i++;
} while( (a/=10)!=0 );
a_length=i;
i=0;
do{
b_digits[i]=b%10;
i++;
} while( (b/=10)!=0 );
if(a_length!=i)
return 0; //even digit number differ between a and b
b_length=i;
for(i=0; i<a_length; i++){
// cycle on all a digits
for (j=0; j<b_length; j++){
// cycle on all the (remaining, valid) b digits
if(a_digits[i]==b_digits[j]){
b_digits[j]=-1;
break;
}
}
if(j==b_length)
return 0;
}
return 1;
}
2nd (gogo STL...):
bool are_permutations (int num1, int num2)
{
/* Must have the same number of digits. */
if ((int) log10 (num1) != (int) log10 (num2))
return false;
std::deque<char> digits1, digits2;
int sorted1 = 0, sorted2 = 0;
while (num1 > 0)
{
digits1.push_back (num1 % 10);
num1 *= 0.1;
}
while (num2 > 0)
{
digits2.push_back (num2 % 10);
num2 *= 0.1;
}
std::sort (digits1.begin (), digits1.end ());
std::sort (digits2.begin (), digits2.end ());
for (std::deque<char>::iterator i = digits1.begin (); i != digits1.end ();
++i)
sorted1 = sorted1 * 10 + *i;
for (std::deque<char>::iterator i = digits2.begin (); i != digits2.end ();
++i)
sorted2 = sorted2 * 10 + *i;
return sorted1 == sorted2;
}
3rd (and the winner is...sprintf, qsort,strlen...):
bool perm(int a, int b)
{
static char b1[1024];
static char b2[1024];
sprintf(b1, "%d", a);
sprintf(b2, "%d", b);
int l1 = strlen(b1);
int l2 = strlen(b2);
if (l1 != l2)
return false;
qsort(b1, l1, 1, cmp);
qsort(b2, l2, 1, cmp);
return !strcmp(b1, b2);
}
