The Next Palindrome

Lets look into another problem of codechef of Medium difficulty. The next palindrome

The problem is you are given a number and you need to return a palindrome just greater than that number. As you all know palindrome number is a number whose reversal(from end to start) is the same number. 121, 1331, 25452 are some examples of palindrome numbers.

So if you are given a number say 120 and you need to give a palindrome just bigger than that number, you now know the answer, it is 121.

But now the question is how to pro grammatically gets the answer. So lets try out.

lets say our given number k is a1a2a3a4a5…..an-1an, now since a1 is the most significant bit we would try to avoid changing it as much as possible but we can change an since it is least significant bit.

so for cases where a1a2a3..an..an-1an < a1a2a3…an/2..a2a1, a1a2a3..an/2..a2a1 is the palindrome. eg. 135 214 < 135 531 so for k = 135 214, 135 531 is the required palindrome.

But for cases where  a1a2a3..an..an-1an > a1a2a3…an/2..a2a1, a1a2a3..an/2..a2a1 is not the required palindrome because it is lesser. Lets divide the number in two halves..

135867 => 135    867

we can change 7 to 1 and 6 to 3 => 135 831 and change 5 and 8 to 6. => 136 631

but what if 5 was 9 and also 8 was 9 139967 => 139 967

we can change 7 to 1 and 6 to 3 => 139 931, now since 139931 < 139967 we need to change 9 to 10 reflecting the similar effect in other 9 of second half

13(10) 967  => 140 967 =do mirror imaging=>140 041

so for even digit numbers algo goes like this,

if an/2 < an/2+1

then increment an/2 to an/2+1 and forward the carry if there is any.

end if

do mirror imaging  of a1a2..an/2 to an/2+1…an-1an

Now for odd digit numbers algo goes like this,

if an-1/2 < an+1/2 +1

then increment an+1/2 by 1 and forward the carry if there is any.

end if

do mirror imaging  of a1a2..an-1/2 to an+1/2+1…an-1an

// thenextpalindrome.cpp : Defines the entry point for the console application.
//
#include <iostream>
using namespace std;

#include<stdio.h>
#include<string.h>
#define S(a,x) scanf("%"#a,&x) //#a expands to "a" we use this bcoz, arguments are not replaced within quoted strings
#define PS(a,x) printf("%"#a" ",x) //print with space
#define PN(a,x) printf("%"#a"\n",x) //print with newline
#define FOR(i,a,b) for( i=a;i<b;i++)
#define FORD(i,a,b) for( i=a;i>=b;i--)
#define REP(i,n) FOR(i,0,n)
#define Max(a, b) ((a>b)?a:b)
#define Min(a, b) ((a>b)?b:a)
#define MAXSIZE 1000001

int main()
{
int n,i, flag;
bool flag9 = true; // true if all 9s
char s[MAXSIZE];
S(d, n);
while (n--)
{
flag = 0; flag9 = true;
S(s, s);
// case 999999..
int len = strlen(s);
FOR(i, 0, len)
{
if (s[i] != '9')
{
flag9 = false;
break;
}
}
if (flag9)
{
cout << "1";
FOR(i, 0, len-1) cout << "0";
cout <<"1"<< endl;
}
else
{
FOR(i, 0, len/2)
{
if (s[i] < s[len - 1 - i])
{
flag = -1;
}
else if (s[i]>s[len - 1 - i])
{
flag = 1;
}
s[len - 1 - i] = s[i];
}
if (flag == 0 || flag == -1)
{
int current = (len - 1) / 2;
while (s[current] == '9')
{
s[current] = '0';
s[len - 1 - current] = s[current];
current--;
}
s[current]++;
s[len - 1 - current] = s[current];
}
PN(s, s);
}
}
return 0;
}

It sometimes gets very irritating when you get so many wrong answers and you are committed to solving the problem without seeing other’s solutions. Even if you see other’s solution you sometimes are not able to figure out what mistake you have done because of which your solution is not getting accepted. Basically you are striving for the testcases which are not passing in your case. Next time we will try to see how to find out those test cases programmatically.

We will write an algo which uses two solution files (one written by you which is not getting accepted and the other written by someone else and is getting accepted) and it runs both the files to find the conflicting tests.

Leave a Reply

Your email address will not be published. Required fields are marked *