Bug in PALIN : Next Palindrome?

Obviously, it got accepted before because "2107" was not one of the test inputs Since there are 10^1000000 possible inputs for this problem, the tests can't really be comprehensive (that's not a problem with the test data, that's a fact of life).

Chances are, your fix for that bug caused your solution to be incorrect on some other input.

Perhaps. As a problemsetter, one of the biggest challenges is coming up with test cases that will cover all the ways people might mess up solving the problem If it makes you feel better, my accepted solution to IMP doesn't even pass the example case in the problem statement.

Well, I didn't know how to solve the problem in every case, but I came up with a method that would find the answer in any case that I could craft. The method had a parameter for the depth to go doing one thing before doing one of two other things, and the main problem was that I didn't know a sure bound for that first thing. I made it "big enough" I hoped and submitted. Then I was curious just how much I had to do it, and so I reduced it down to once and it still was accepted (but the example data required twice).

The main problem here was probably that the person who wrote the problem knew how to really solve it, and they didn't really know how someone like me that didn't know how to solve it would approach it.

Well my accepted code gives 2112 for 2107.

From what I can tell, there are only 7 possible types of test cases (I'm yet to find out if my solution works here though due to technicalities), but I'd appreciate being proven wrong

So generating correct test data shouldn't be too hard given at least those seven cases -- I wouldn't mind knowing how many programs would fail in various tests with updated data.

And I'd say what I think they are, but don't want to give away too many clues to others

There are only 7 possible types of test cases, you THINK, based on YOUR implementation. But another person's algorithm might have a completely different set of special cases or weaknesses. People are really creative when it comes to inventing wrong ways to solve a problem

Any bug in my code? Please help

#include<stdio.h>
char num[1000005];
int len;
void nextpalin()
{
	int i,j,k;
	for(i=0,j=len-1;i<=j;++i,--j)
	{
		if(num[i]<num[j])
		{
			for(k=j-1;num[k]=='9';num[k]='0',--k);
			++num[k];
		}
		num[j]=num[i];
	}
}
int main()
{
	char ch;
	int i,j,test,flag;
	for(scanf("%d%*c",&test);test--;)
	{
		for(len=-1,flag=1;(ch=getchar())!='\n'&&ch!=EOF;num[++len]=ch)
			if(ch!='9')
				flag=0;
		num[++len]='\0';
		if(flag)
		{
			for(putchar('1'),i=len-1;i--;putchar('0'));
			printf("1\n");
		}
		else
		{
			for(i=len-1;num[i]=='9';num[i]='0',--i);
			++num[i];
			nextpalin();
			nextpalin();
			printf("%s\n",num);
		}
	}
	return 0;
}

Firstly , for this problem ,the input data can contain upto 1000000 digits. What does this mean ? the maximum input is 1000000 or the no of digits in the integer is 1000000?

secondly , I believe I have a fullproof solution to this problem and yet i get a wrong answer. Is there any way to find which input caused the wrong answer ?

The latter; the input can be up to 10^1000000.

If you get a WA then your solution isn't foolproof The only way to find your bug (which is a very important step in solving problems like these) is to debug your code, come up with boundary cases, write a brute force solver to compare with for small inputs, etc.

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 );

}
}

HELLO!!!
This is compiled code but it isn’t producing any output .
CAN SOMEONE PLEASE HELP ME OUT HERE …

import java.util.;
import java.lang.;

class Main
{
public static void main (String[] args)
{
try{
Scanner kb=new Scanner(System.in);
int t=kb.nextInt();
int s=0;
while((–t)>0)
{
int k=kb.nextInt();

		for(int i=k+1;i<1000000;i++)
		{
			int c=i,n=0;
			
			while(i!=0)
			{
			int r=i%10;
			 n=n*10+r;
			 i=i/10;
			}
           
			if(c==n)
			{
				System.out.println(c);
			   break;
			}
			else 
			{
			continue;
			}
		}
		
	}
	}
	catch(Exception e)
	{
		
	}
}

}

could anyone tell me why its getting TLE

for _ in range(int(input())):
s=input()
j=[i for i in s]
h=[i for i in s]
if len(s)%2==0:
for i in range(len(s)//2):
j[i]=j[len(s)-i-1]
h[len(s)-i-1]=h[i]
else:
for i in range(len(s)//2-1):
j[i]=j[len(s)-1-i]
h[len(s)-1-i]=h[i]
g=’’.join(j)
p=’’.join(h)
if len(s)%2==1:
d=s[:len(s)//2+1]
if d!=‘9’*(len(s)//2+1):
d=int(d)+1
d=str(d)
k=d[::-1]
for i in range(1,len(k)):
d=d+k[i]
else:

        d=int(d)+1
        d=str(d)
        k=d[::-1]
        for i in range(2,len(k)):
            d+=k[i]
else:
    d=s[:len(s)//2]
    if d!='9'*(len(s)//2):
        d=int(d)+1
        d=str(d)
        k=d[::-1]
        for i in range(len(k)):
            d=d+k[i]
    else:

        d=int(d)+1
        d=str(d)
        k=d[::-1]
        for i in range(1,len(k)):
            d+=k[i]
d=int(d)
g=int(g)
p=int(p)
#print(d,g,p)
f=int(s)
l=[]
for i in [d,g,p]:
    if i>=f:
        l.append(i)
#print(l)
l.sort()
for i in l:
    if i>f:
        f=i
        break

print(f)