SPOJ 5 - PALIN - The Next Palindrome

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

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

Output

For each K, output the smallest palindrome larger than K.

Example

plaintext

Input:
2
808
2133

Output:
818
2222

Solution

Let $K = X(1)X(2)..X(mid)..X(n)$

First, compare $R = X(1)X(2)..X(mid)..X(2)X(1)$ with $K$ .

If $R > K$ then you got the answer, else try $X(1)X(2)..X(mid) + 1$

Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN_K 1000000

int compare(char *num_a, char *num_b, int len) {

  int i;

  for (i = 0; (i < len) && (num_a[i] == num_b[i]); i++);

  if (i == len) {
    return 0;
  } else {
    return num_a[i] < num_b[i] ? -1 : 1;
  }
}

char *next_palindrome(char *number) {

  int len = strlen(number);
  int i, j, l = 1, r = len;

  static char result[MAX_LEN_K + 3];

  result[0] = '0';

  for (i = l, j = r; i <= j; i++, j--) {

    result[j] = result[i] = number[i - l];
  }

  result[r + 1] = '\0';

  if (compare(result + l, number, len) <= 0) {
  
    for (i = (l + r) >> 1; i >= 0; i--) {

      if (result[i] == '9') {
        
        result[i] = '0';
      } else {
        
        result[i]++;
        break;
      }
    }
    
    if (result[0] != '0') {
      --l;
    }

    for (i = l, j = r; i < j; i++, j--) {

      result[j] = result[i];
    }
  }

  return result + l * sizeof(char);
}

int main(int argc, char **argv) {

  int t;
  char k[MAX_LEN_K + 1];

  scanf("%d", &t);

  while(t--) {

    scanf("%s", k);

    printf("%s\n", next_palindrome(k));
  }

  return 0;
}