Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com

And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Thursday, October 23, 2014

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

3 comments:

  1. import java.util.*;
    import java.lang.*;

    class Main
    {
    public static void main (String[] args) throws java.lang.Exception
    {
    Scanner sc = new Scanner(System.in);
    int t,i,k,sum=0;
    int m = 0;
    t = sc.nextInt();
    while(m0)
    {
    sum=sum*10 + i%10;
    i=i/10;
    }

    if(sum==i)
    {
    System.out.println(i);
    break;
    }
    }
    m=m+1;
    }
    }
    }

    Why isn't it working ?

    ReplyDelete
  2. while(m<t) in line 11

    ReplyDelete

Your comment is valuable to us