PALIN - The Next Palindrome

It is a solution to the 5th and one of most attractive problem to novice, as well as experienced hacker if they haven't done with it of SPOJ domain. It is a problem on string matching in which we are to find the very next Palindromic Number ( Number which reads the same from either sides ).

There  are many ways to carry out this problem. But, I started with isolating the numbers into different categories as :

1. Palindromic Number
    If the given number is itself palindromic then we'll only have to find the next palindromic number
 
    So, Let us start :
    1. Check the length of the string ( even and odd )
    2. If length is odd then check if the middle integer is less then 9 on not, if yes then increase its value by 1, and we are done. Print the String ( Number) else follow the next step.
    3. Now take two pointers (i,j) which are pointing :
                                           
                                                 if(length is odd) {
                                                          i = length/2 - 1;
                                                          j = length/2 + 1;
                                                }

     /*   Here onwards, we are considering string indexing starts with '0' (zero) and ends at lenght-1  */

                                               else {
                                                           i =length/2 - 1 ;
                                                           j = length/2;
                                                       }

   4.  Now, i believe you we'll be getting the logic, but if you don't check  the code because it not possible to explain the elementary logic.

2. Non-Palindromic Number
    Separate out Even and Odd length Number.

1. If Length is Odd
 
    find RESULT which is defined as :
 
    RESULT =  number_formed_by_reversing_string( index_('0') , index_(length/2 - 1) ) minus number_formed_by_string(index_(length/2 + 1) , index_(length - 1) ) ;

  if(RESULT > 0 ) {
           Check the code line  1:
}

else {
          Check the code line 2 :
}

2. If Length is Even
          Check the code line 3:

  At last print the number string.

#include<bits/stdc++.h>

char str[1000005];

int main()
{
    int t,i,j;

    scanf("%i",&t);

    while(t--) {

        scanf("%s",str);

        int lenght = strlen(str);

        j = lenght;
        i = -1;

        while(++i <= --j) {
            if(str[i] != str[j]) {
                break;
            }
        }

        if(j < i) {
            /*   Number is palindrome   */

            if(lenght & 1) {
                /* odd lenght  */

                if(str[lenght/2] < '9'){
                    /* check the middle one not 9 */

                    str[lenght/2]++;

                    printf("%s\n",str);
                }

                else {
                    str[lenght/2] = '0';

                    i = lenght/2 - 1;
                    j = lenght/2 + 1;

                    while(i >= 0) {

                        if(str[i] < '9') {
                            str[i]++;
                            str[j]++;
                            break;
                        }

                        else {
                            str[i] = str[j] = '0';
                        }

                    i--;
                    j++;
                    }

                    if(i < 0) {
                        printf("1");

                        i = lenght;
                        while(--i > 0) {
                            printf("0");
                        }

                        printf("1\n");
                    }

                    else {

                        printf("%s\n",str);
                    }
                }
            }

            else {
                /*  even lenght  */

                    i = lenght/2 - 1;
                    j = lenght/2;

                    while(i >= 0) {

                        if(str[i] < '9') {
                            str[i]++;
                            str[j]++;
                            break;
                        }

                        else {
                            str[i] = str[j] = '0';
                        }

                    i--;
                    j++;
                    }

                    if(i < 0) {
                        printf("1");

                        i = lenght;
                        while(--i > 0) {
                            printf("0");
                        }

                        printf("1\n");
                    }

                    else {

                        printf("%s\n",str);
                    }
            }
        }

        else {
            if(lenght & 1) {
                i = lenght/2 - 1;
                j = lenght/2 + 1;
            }

            else {
                i =lenght/2 - 1;
                j = lenght/2;
            }

            int flag;

            while(i >= 0) {

                if(str[i] - str[j] > 0) {
                    flag = 1;
                    break;
                }

                else if( str[i] - str[j] < 0 ) {
                    flag = 2;
                    break;
                }

                i--;
                j++;
            }

            if(lenght & 1) {
                i = lenght/2 - 1;
                j = lenght/2 + 1;
            }

            else {
                i = lenght/2 - 1;
                j = lenght/2;
            }

            if(flag == 1) {    /*  line 1*/
                while(i >= 0) {
                    str[j] = str[i];

                    i--;
                    j++;
                }
            }

            else if(flag == 2 && lenght&1 && str[lenght/2] < '9'){    /* line 2*/
                str[lenght/2]++;

                i = lenght/2 - 1;
                j = lenght/2 + 1;

                while(i >= 0) {
                   str[j] = str[i];
                   i--;
                   j++;
                }
            }

            else {                          /* line 3   */

                if( lenght & 1) {
                    str[lenght/2] = '0';
                }

                while(i >= 0) {
                    if(str[i] < '9') {
                        str[i]++;
                        str[j] = str[i];
                        break;
                    }

                    else {
                        str[i] = str[j] = '0';
                    }
                    i--;
                    j++;
                }

                while(i >= 0) {
                    str[j] = str[i];

                    i--;
                    j++;
                }
            }

            printf("%s\n",str);
        }
    }

    return 0;
}