Next Palindrome Problem

help
1

I was trying to solve The Next Palindrome problem.
I was expecting my submission to get correct, but eventually it isn’t.
Here is my solution. CodeChef: Practical coding for everyone.
Is this a good method to find the next palindrome?

#include <bits/stdc++.h>
using namespace std;

bool isp(int k) {
    int x=0, y=k;
    while(y!=0) {
        x = (x*10) + (y%10);
        y = y/10;
    }
    if(x == k)
        return true;
    return false;
}

int main() {
	int t, k, i;
	cin >> t;
	while(t--) {
	    cin >> k;
	    for(i=k+1; i<INT_MAX; i++) {
	        if(isp(i)) {
	            cout << i << endl;
	            break;
	        }
	    }
	}
	return 0;
}
2

From the problem description - how big a number can K be? How big a value can an int hold?

1 Like
3

If K is small upto 10000, is this a good method to solve?
Is there any other better method?

4

No, this is not an optimized solution
go through this link

5

yes it should work. But the problem says k is 1000000 “digits” long

6

First of all I suggest you to read the problem statement again & carefully, in the problem it is given that “K will have at-most 10^6 digits”, from this information, you can conclude that in C/C++ you cannot store this large value in a 64-bit unsigned integer.

Coming to your code, the logic which you have used is, you are looping through k+1 to maximum value the 32-bit signed integer can store (INT_MAX) and for reversing every i using isp(i) function, checking whether the reverse of i is equal to i or not. If equal then palindrome otherwise not palindrome.

Your algorithm is right but it will not give right answer for every case because you have not handled all of the scenarios which can happen, i.e.

  1. While running the for loop, you are making an assertion that, for each k, the next smallest palindromic number will always lie between [k+1,INT_MAX], but it’s not true.
  2. What if the input to the algorithm is INT_MAX value itself, then your program will not give the right answer.
    You can check for above scenarios yourself.

Some of the test-case for which you can check whether your program is giving the right-answer or not are as follows:

14
9 \implies 11
75 \implies 77
776 \implies 777
4891\implies 4994
92764 \implies 92829
999539 \implies 999999
7059657 \implies 7060607
48756572 \implies 48766784
633149324 \implies 633151336
2096785014 \implies 2096886902
80448359477 \implies 80448384408
237762850363 \implies 237763367732
7730351516591 \implies 7730351530377
79541453924626 \implies 79541455414597

So, you need think of another algorithm which will solve this problem.
Whenever you encounter the problem in which the input is large enough that cannot be stored in a pre-defined integer variables, always look for patterns by solving some of the test-cases yourself randomly, it will give you a fair idea, of what is going on.

For this problem, when you look for some of examples like [99,4444,2313,102]. You will observe that there are 4 cases which you need to handle in order to solve the problem.
Case\;1: \text{If the input is 9,99,999 or 9 repeated n times}
In this case the next smallest palindromic number will be:
9 \implies 11
99 \implies 101
999 \implies 1001
As you can see there is a pattern, i.e whenever the input is [9,99,999,...], then answer will be: 1 \; \text{followed by 0's then 1} , number of 0's will be total number of 9 present in the number - 1.

Case\;2: \text{If the given number is palindrome like [11,101,4444,495,1991...]}
In this case the next smallest palindromic number will be:
11 \implies 22
101 \implies 121
4444 \implies 4554
495 \implies 505
1991 \implies 2002
You need to increase the middle element by 1. Do take care of the case when the middle element is 9, because you need to forward the carry to left, update the value, and take the mirror image of that to the respective location on the right.

Case\;3: \text{If in the given number left-sub-array is greater than the right-sub-array}
\text{like [531,5431,54321]}
In this case the next smallest palindromic number will be:
531 \implies 535
5431 \implies 5445
54321 \implies 54345

You need to take the mirror of the left-subarray and copy it to the right-subarray.

Case\; 4: \text{If the elements of the left-subarray is smaller than right-subarray like [135,1345,12345]}
In this case the next smallest palindromic number will be:
135 \implies 141
1345 \implies 1441
12345 \implies 12421

Increment the value of mid by one, and copy the mirror image of left-subarray to right-subarray. Do take care of the case when the middle element is 9, because you need to forward the carry to left, update the value, and take the mirror image of that to the respective location on the right.

You can look at the source-code in C programming at the link: The Next Palindrome Solution

1 Like