Find the next palindrome. Input is an integer and output should be the palindrome integer which is higher than the input.
Example:
Input: 12345
Output:12421
Input:111
Output: 121
Solution:
Let the Input be "ABCDEFGH". Now divide it into two equal parts "ABCD" and "EFGH". let us call the higher part as "ABCD" and lower part as "EFGH". Now reverse the higher part to get "DCBA". Check if "DCBA" greater than "EFGH" or not.
Case 1: DCBA is greater than EFGH
return "ABCDDCBA" as the output.
Case 2: DCBA is lower than or equal to EFGH
Add 10000 to "ABCDEFGH" to "HIJKEFGH" and apply the above logic to return "HIJKKJIH"
10000 is added to ensure that the middle digit is changed. Added index is generally 10^(numOfDigits/2).
Example 1:
112100
higher = 112
lower = 110
reverse higher = 211
So output 112211
Example 2:
1121
higher = 11
lower = 21
reverse higher = 11
So add 100 to change the lowest of the higher part. to get 1221. So output 1221 as the next palindrome.
Example 3:
45621
higher = 45
lower = 21
reverse higher = 54
so return 45654
Example 4:
45678
higher = 45
lower = 78
reverse higher = 54
so add 100 to get 45778 . so return 45754.
This algo gives correct answer to most of the inputs. But consider 9999 or 99999. It fails in these inputs. These cases are special
ReplyDeletenot like that ...
ReplyDeleteif the middle digit is 9 then this algo doesnt work... :P
sorry i was wrong the authors algorithm works....
ReplyDelete#include
int ten(int s)
{
int i=1,product=1;
for(i=1;i<=s;i++)
product=product*10;
return product;
}
int main()
{
int n=0,num=0,b=0,c=0,d=0,i=1,input=0,upper=0,lower=0,output=0;
scanf("%d",&input); //1234 /12345
num=input;
while(num!=0)
{
n++;
num/=10;
}
num=input;
printf("\n n=%d",n);
lower=num%ten(n/2);
printf("\nlower=%d",lower); //34 45
c=num/ten(n/2); //12 123
d=c;
if(n%2!=0)//if not even digits
d=c/10; // 12 12
printf("\n%d%d",c,d);
while(d!=0)
{
upper=upper*10+(d%10);
d=d/10;
}
printf("\nupper=%d",upper);//21 21
if(upper>lower)
{
output=c*ten(n/2)+upper;
}
else
{
c=c+1; //124
d=c;
upper=0;
if(n%2!=0)
d=d/10; //12
while(d!=0)
{
upper=upper*10+(d%10);
printf("\nd=%d",d);
d=d/10;
}
output=c*ten(n/2)+upper;
}
printf("\noutput=%d",output); //1331 12421
getch();
}
the algo works this way if the middle digit is 9
ReplyDeletecase -1 898
case -2 999
In case -1 898 add 10^(3/2)=10 is 908
now apply the algo, 9>8 so 909 is next palindrome
In case-2 999 add 10^(3/2)=10 is 1009
higher half is 10 reverse it 01
and 1001 >999 so 1001 is next palindrome