More details here.
There, I came across this problem which looked quite interesting. Basically, the challenge is, given a number n, we've got to find the palindromic number which comes after this.
Some definitions:
Palindromic number: A number that reads the same either way, like 12421, 57375, 8448, 146641, etc.
"comes after this": the palindrome number must be greater than the given number - given 12321, we must find the next palindrome and not return 12321 itself as the answer.
Ok, with those made clear, let's dive into the problem.
On first sight, it seems simple enough: iterate from n+1 checking if each number is a palindrome. Stop when you find a palindrome.
Unfortunately, that strategy is too slow for our purposes - SPOJ clearly states the inputs can be very huge, in which case this brute force would probably not be able to complete it within the given 9 seconds.
Anyway, we are programmers, and must seek more efficient ways when they exist. Here, it does seem there must be a way to find the next palindrome given a number. What would it be?
My first thought was, simply mirror the number around its centre. Then, we'd surely end up with a palindromic number.
What I mean is, given a number 16310, mirror the first half values across the central '3' to give 16361. If the number has an even number of digits, just mirror it about the centre of the number, like 3628 to 3663.
That strategy works as long as the resulting 'mirror-imaged' value is greater than the original number. What if it results in a number less than (or equal to) the original? Say, for 41258, it would give 41214, which is less than the original number. Or 12321, which would give 12321 itself, which is equal to the original number.
So my next strategy was, if simple mirror-imaging fails, increment the middle digit and then do a mirror image. So, 41258 would become 41314. 12321 would be 12421.
But again, there's a problem with this approach. What if the number had even number of digits? There is no middle digit to increment. Let's say the number was 4265. It's simple to see that, instead of the middle digit, if we increment the digit to the left of the middle (2 here), and do the mirror image, we'll have the palindrome we want: 4334 in this case.
So far, so good.
Now, onto a big issue: 9. Yes, the digit nine. We saw that when the simple mirroring fails, we increment the middle (or left to middle) digit. Now, what do we get when we increment 9? 10. Oops! We can't put a 10 where 9 was. Want proof? Try 41968. Simple mirroring would give 41914, no luck there. Incrementing the 9 to 10 would give 411014, not a palindrome even. And also, it's surely false that there's no palindrome between 41,968 and 411,014 (that's between forty one thousand and four hundred and eleven thousand).
So, what do we do? Luckily, something we learnt in elementary school - carrying over - seems to help here too. Wherever the 10 occurred, keep the 0 there itself, carry over the 1 to the previous digit. So here, 41968 would become 42068 which on applying mirroring would give 42024.
EDIT: Turns out if I finish the increment and carrying over parts fully, then mirror image the number according to how many digits it now has, the 9999 cases take care of themselves with the original algo itself - no 'special cases' needed. :)
So, I believe this is the complete algorithm to find the next palindrome given a number. I have not thought through the steps very carefully, so if you see any flaws, kindly point them out...
I'm trying to code this thing in the Lisp programming language, so I'm taking baby steps towards the solution. As of now, I'm yet to implement the carrying over for 9 part alone. And I don't have any idea how complex that is going to be.
Update: I finished coding this in Lisp, but lost the code somewhere. I coded it again in Python now, which is available here. I've put in a lot of comments so as to make it somewhat easily understandable. Hope this helps the doubting Thomases believe. :)
By the way, my GATE solutions blog now has full feed access, which means you can read it fully without leaving the comfort of your RSS reader.
Happy coding :)
24 comments:
how about 100 or 1000,will it give 101 I hope it doesnt it gives 111/1111.
@Srinath:
In the case of 100 and 1000, the first simple strategy - mirroring the number about its centre - would do the trick. For 100 it would give 101, and for 1000, 1001, which are the correct answers... So yes, it will give the correct answer, not 111 or anything. :)
but then how do you filter tose numbers from others and what about 9 99 999?
i'm working on the same problem, the algorithm is clearly flawed...
how about 890?
u'll get 909, skipping over 898...
i'm just 2 steps below breakthrough, i just know it. :)
Took me a while but i figured it out...lemme know if your interested in the solution. or figured it out yourself
Regards.
St0le: I would like to know how you figured it out.
The first step of the algorithm is to try mirroring the number about it's center. For 890, that step itself would give 898, which is the correct answer.
Only if we get a number smaller than the original number in that step, (for eg: when input is 899), we proceed to the more complicated steps.
The explanation is probably not clear since there are so many people getting confused. I'll include a pseudocode as soon as I get some spare time.
and how about tests such as "99999"????
99999 is already a palindrome
thank you.
i got my solution accepted after reading this blog.
u have explained it very nicely.
Thank you :)
#include
#include
#include
#include
#include
int
nin (long long num)
{
int i = 1;
while ((num / 10) != 0)
{
i++;
num = num / 10;
}
return i;
}
char *
ll2s (long long num)
{
int s = nin (num);
int i = 0;
char *arr = (char *) malloc ((s + 1) * sizeof (char));
while (i < s)
{
arr[s - i - 1] = 48 + (num % 10);
num = num / 10;
i++;
}
arr[s] = '\0';
return arr;
}
long long
s2ll (char *arr)
{
int i = 0;
long long val = 0;
while (i < strlen (arr))
{
val = val * 10 + ((char) arr[i] - 48);
i++;
}
return val;
}
void
strncopy (const char *src, char *dest, int start, int n)
{
int i = 0;
while (i < n)
{
dest[i] = src[start + i];
i++;
}
dest[n] = '\0';
}
int
cg (char *v1, char *v2)
{
int i = 0, j = 0;
i = strlen (v1);
while (j < i)
{
if (v1[j] == v2[j])
{
j++;
}
else if (v1[j] < v2[j])
{
return -1;
}
else
{
return 1;
}
}
}
void
strrev (char *src, char *dest)
{
int i = 0;
while (i < strlen (src))
{
dest[i] = src[strlen (src) - 1 - i];
i++;
}
dest[strlen (src)] = '\0';
}
int
cp (char *a)
{
int i = 0;
while (a[i] == a[strlen (a) - i - 1] && (i < (strlen (a) / 2)))
{
i++;
}
if (a[i] != a[strlen (a) - i - 1])
return 0;
else
return 1;
}
char *
ci (char *val)
{
int i = strlen (val), j = 0;
while (i > 0)
{
if (val[j] != '9')
{
break;
}
j++;
i--;
}
if (i == 0)
{
j = strlen (val);
val = realloc (val, j + 1);
val[j] = '\0';
i = 1;
while (i <= j)
{
val[i] = '0';
i++;
}
val[0] = '1';
}
else
{
j = strlen (val);
j--;
while (val[j] == '9')
{
val[j] = '0';
j--;
}
val[j] = val[j] + 1;
}
return val;
}
char *
palin (char *val)
{
int i = 0;
char *v1, *v2;
// scanf ("%lld", &val);
val = ci (val);
i = strlen (val);
char *s1, *s2, *s3, *s4, *s5, *s6;
s3 = val;
s1 = (char *) malloc (sizeof (char) * ((i / 2) + 1));
s2 = (char *) malloc (sizeof (char) * ((i / 2) + 1));
s4 = (char *) malloc (sizeof (char) * ((i / 2) + 1));
strncopy (s3, s2, ceil ((float) i / 2), i / 2);
strncopy (s3, s1, 0, i / 2);
strrev (s1, s4);
v1 = s4;
v2 = s2;
s5 = (char *) malloc (sizeof (char) * strlen (s1) * 2);
s6 = (char *) malloc (sizeof (char) * ((i / 2) + 1));
if (2 * strlen (s1) == strlen (s3))
{
if (cg (v1, v2) == 0)
{
s5 = s3;
}
else if (cg (v1, v2) == 1)
{
strcat (s5, s1);
strcat (s5, s4);
}
else
{
// strncopy (s3, s6, 0, i / 2);
s2 = ci (s1);
// s5 = (char *) malloc (s2, sizeof (char) * i);
strrev (s2, s4);
strcat (s5, s2);
strcat (s5, s4);
}
}
else
{
if (cg (v1, v2) == 0)
{
s5 = s3;
}
else if (cg (v1, v2) == 1)
{
s2 = (char *) realloc (s2, 2 + i / 2);
strncopy (s3, s2, 0, (1 + i / 2));
// s2 = ll2s (s2ll (s2));
strrev (s1, s4);
s5 = (char *) realloc (s5, i);
strcat (s5, s2);
strcat (s5, s4);
}
else
{
s2 = (char *) realloc (s2, 2 + i / 2);
strncopy (s3, s2, 0, (1 + i / 2));
s2 = ci (s2);
strrev (s1, s4);
s5 = (char *) realloc (s5, i);
strcat (s5, s2);
strcat (s5, s4);
}
}
return s5;
}
int main ()
{
int index = 0;
int i = 0, j = 0;
//char* val;
scanf ("%d", &index);
j = i = index;
char *arr[index]; //=(char**)malloc(sizeof(char*)*i);
char *c[index];// = (char **) malloc (sizeof (char *) * i);
i=0;
while (index>0)
{
arr[i]=(char*)malloc(sizeof(char)*1000001);
scanf ("%s", arr[i]);
i++;
index--;
}
i = 0;
while (i < j)
{
printf ("%s\n", palin(arr[i]));
i++;
}
/*
char *a;
a=(char*)malloc(sizeof(char)*1000001);
scanf("%s",a);
printf("%s",palin(a));
*/
}
/******************************
i am sorry for poor documentation..i have written it for codechef
should compile it with following command as i have written it in c99 for making it compatible for long inputs upto 10^10
gcc -std=c99 -lm
the code mainly takes
1st input as number of test cases
and next lines as numbers whose palindromes are to be printed..
Please do report me for bugs
a sample test case is
3
100
253
441
*******************************/
here is a link to the file which prints palindromes ..i have written it in c99 for printing large palindromes upto 10^10
you have to compile it with
"gcc -std=c99 -lm "
http://cid-7fd0c50da02ebc66.office.live.com/embedicon.aspx/.Public/spgn.c
first input is number of test inputs and rest are inputs
here is a sample test case
3
118
921
52354
#include
#include
#include
using namespace std;
int isPalindrome(string s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s[i] != s[j]) {
return 0;
}
}
return 1;
}
int main(){
int t;
cin>>t;
for(int j=0;j>n;
for(int i=n+1;i<=1000002;i++){
string s;
int num;
stringstream ss,ss2;
ss<>s;
int r=isPalindrome(s);
if(r==1){cout<<i<<endl;goto out;}
}
out:;
}
system("pause");
return 0;
}
@mani..thats brute force!!
Thnx i am grateful to you for providing such a marvelous solution to this problem.. The people who r seeking flaws in this solution are those who need spoon feeding .. You have done your job really well..
Please check this code. i have coded this in turbo c and i am getting correct answers for all cases but still it is being rejected by Code chef due to some "runtime error" ... i will be thankful to you
#include
#include
#include
#define MAXLEN 20
void main()
{
char num[MAXLEN],num2[MAXLEN];
unsigned long int t,len,j;
int i,carry=0;
clrscr();
scanf("%lld",&t);
for(i=1;i<=t;i++)
{
fflush(stdin);
fflush(stdout);
carry=0;
fgets(num,MAXLEN,stdin);
//puts("viny");
strcpy(num2,num);
len=strlen(num)-1;
//puts(num);
for(j=0;j<=len/2-1;j++)
{
//printf("%c",num[j]);
num[len-j-1]= num[j];
}
if(strcmp(num,num2)<=0)
{
if(num[len/2]=='9')
{
if(len%2==0)
j=len/2-1;
for(;j>0||j==0;j--)
{
if(num[j]=='9')
{
num[j]='0';
carry=1;
}
else
{
if(carry==1)
{
num[j]++;
carry=0;
}
else
break;
}
num[len-j-1]=num[j];
}
num[len]='\0';
//printf("%d",carry);
}
else
{
num[len/2]++;
//printf("%lld",len);
if(len%2==0)
{ num[len/2-1]++;
num[len/2]=num[len/2-1];
}
}
}
if(num[0]=='0')
{
num[0]='1';
puts(strcat(num,"1"));
}
else
{
puts(num);
}
//fflush(stdin);
}
getch();
}
Hi Vineet,
http://cid-7fd0c50da02ebc66.office.live.com/embedicon.aspx/.Public/spgn.c
This is C99 code.
gcc -std=c99 -lm
the code mainly takes
1st input as number of test cases
and next lines as numbers whose palindromes are to be printed..
Please do report me for bugs
a sample test case is
3
100
253
441
Sorry but there is an error in this program.Try 6336 as input.
You'll get 6336 as output but instead it should give 6446 as output.
hey its very easy in case of 999 or 9999. Consider this just add 1 to 999 or 9999, i.e. we get 1000 and 10000. and then just mirror it as u did earlier.
I hope there is nothing wrong in it.
Please comment/suggest/correct me if i m wrong.
This works based on the fact that you can compare the mirrored number and the original number(could be done in python, but not in C/C++). You could have posted a more general solution, which involves comparing during mirroring and then doing the "complicated procedure" :P Just saying...
Hi
I implemented the exact same algorithm in python before stumbling upon your blog, but it exceeds spoj's timelimit of 9sec for the code. Have you been able to submit your code on spoj?!
Hi,
I implemented the exact same algorithm on python before stumbling upon your blog, but it seems to be exceeding spoj's timilimit for the code. Have you been able to submit your code on spoj?
Post a Comment