Next Palindrome
Problem Code: NXTPALIN
I pre-computed all the palindrome numbers and then tried solving it.
It passed the sample test cases …but i guess there are some corner cases… How to solve this ??
#include<bits/stdc++.h>
using namespace std;
#define MAX 100009
bool tu_bta(int a)
{
string s = to_string(a);
string left = s;
reverse(s.begin(),s.end());
string right = s;
if(left == right)
{
return true;
}
return false;
}
int main()
{
// mai precompute kr skta hun shyd
bool arr[MAX] = {false};
for(int i=1;i<MAX;i++)
{
bool res = tu_bta(i);
arr[i] = res;
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
for(int i=n+1;i<MAX;i++)
{
if(arr[i])
{
cout<<i<<endl;
break;
}
}
}
return 0;
}
This is a similar issue, I’ve added the required details and also my AC soln.
The code requires O(logN) complexity for each test case, your code does it in O(N). Hope it helps
okkkk thank you.
Ill try to optimize.
I don’t think time complexity will be a problem here , I think the question is incorrectly written because if we input a palindrome number it is expecting that number as the answer but according to the statement the answer should be the next palindrome.
@shivam7ms just try to change this I think it would be AC.
2 Likes
yess…thanks a lot
But…still is thr any better way to solve this ?? i mean…faster way ??
Faster way can be storing all the palindromes in an array and then applying binary search for each query.
So for each query logN time but overall time complexity will be O(NlogN), as also suggested in the earlier comments.
1 Like