Category: c

Finding the next Palindrome

Given a positive palindrome number P up to 10,000,000 digits. Find the next palindrome.

Input

The first line contains integer n, the number of test cases. Integers P are given in the next t lines.

Output

For each P, output the next palindrome larger than P.

Example

Input:
12
1
9
12
99
101
999
1001
808
900000000000000000000000000000000000009
123454321
1999999999991
199999999991

Output:
2
11
23
101
111
1001
1111
818
900000000000000000010000000000000000009
123464321
2000000000002
200000000002

#include 
#include 
#include 
#include 
int main(void) {
	char * number;
	int instances;
	scanf("%d", &instances);
	int i;
	for (i = 0; i < instances; i++){
		number =  malloc(sizeof(char)*(10000000));
		scanf("%s", number);
		int len = strlen(number);
		int k;
		int flag = 1;
		
		// In case the number is all 9s
		for (k = 0; k < len; k++){
			if (number[k] != '9'){
				flag = 0;
			}
		}
		
		if (flag == 1){
			printf("1");
			for (k = 0; k < len - 1; k++){
				printf("0");
			}
			printf("1\n");

		}
		else{
			int left = (int)ceil((double)len / 2)-1;
            int right;
			if(len%2 == 0)
			   right = left+1;
			 else
			   right = left;
			
			for (k = 0; k <= (int)floor(len / 2.0); k++){
				// if middle numbers are not 9
				if ((number[left] != '9') && (number[right] != '9')){
					int numL = number[left];
					int numR = number[right];
					number[left--] = (char)(numL + 1);
					number[right++] = (char)(numR + 1);
					break;
				}
				else{ // if middle numbers are 9
					number[left--] = '0';
					number[right++] = '0';
				}
			}
			printf("%s\n", number);
		}
	}
	free(number);
	return 0;
}

Code on ideone