Next Palindrome
Why my code shows Wrong Answer, I’ve tested a lot of test cases and all are giving correct answer . Please help me find my mistake.
Here is my code :
//The Next Palindrome
#include<bits/stdc++.h>
using namespace std;
// A utility function to print an array
void printArray (int arr[], int n);
// A utility function to check if num has all 9s
int AreAll9s (int num[], int n );
// Returns next palindrome of a given number num[].
// This function is for input type 2 and 3
void generateNextPalindromeUtil (int num[], int n )
{
// find the index of mid digit
int mid = n/2;
// A bool variable to check if copy of left side to right is sufficient or not
bool leftsmaller = false;
// end of left side is always 'mid -1'
int i = mid - 1;
// Beginning of right side depends if n is odd or even
int j = (n % 2)? mid + 1 : mid;
// Initially, ignore the middle same digits
while (i >= 0 && num[i] == num[j])
i–,j++;
// Find if the middle digit(s) need to be incremented or not (or copying left
// side is not sufficient)
if ( i < 0 || num[i] < num[j])
leftsmaller = true;
// Copy the mirror of left to tight
while (i >= 0)
{
num[j] = num[i];
j++;
i--;
}
// Handle the case where middle digit(s) must be incremented.
// This part of code is for CASE 1 and CASE 2.2
if (leftsmaller == true)
{
int carry = 1;
i = mid - 1;
// If there are odd digits, then increment
// the middle digit and store the carry
if (n%2 == 1)
{
num[mid] += carry;
carry = num[mid] / 10;
num[mid] %= 10;
j = mid + 1;
}
else
j = mid;
// Add 1 to the rightmost digit of the left side, propagate the carry
// towards MSB digit and simultaneously copying mirror of the left side
// to the right side.
while (i >= 0)
{
num[i] += carry;
carry = num[i] / 10;
num[i] %= 10;
num[j++] = num[i--]; // copy mirror to right
}
}
}
// The function that prints next palindrome of a given number num[]
// with n digits.
void generateNextPalindrome( int num[], int n )
{
int i;
// Input type 1: All the digits are 9, simply o/p 1
// followed by n-1 0's followed by 1.
if( AreAll9s( num, n ) )
{
printf( "1");
for( i = 1; i < n; i++ )
printf( "0" );
printf( "1" );
}
// Input type 2 and 3
else
{
generateNextPalindromeUtil ( num, n );
// print the result
printArray (num, n);
}
}
// A utility function to check if num has all 9s
int AreAll9s( int* num, int n )
{
int i;
for( i = 0; i < n; ++i )
if( num[i] != 9 )
return 0;
return 1;
}
/* Utility that prints out an array on a line */
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
cout<<arr[i];
printf("\n");
}
// Driver Program to test above function
int main()
{
unsigned long long int t;
cin>>t;
unsigned long long int n,x;
next:
while(t--)
{
cin>>n;
x=n;
int arr[100000]={0};
int d=0;
while(x)
{
x=x/10;
d++;
}
if(d==1||d==0){
cout<<n;
goto next;}
for(int i=d-1;i>=0;i--)
{
arr[i]=n%10;
n=n/10;
}
generateNextPalindrome( arr, d );
}
}
