SPOJ: smallest palindrome larger than a given number

Question

I am working on the SPOJ palindrome question. I'm using JAVA to solve it. The problem:

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

Input:

2 
808 
2133

Output:

818  
2222

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main{
    public static void print(String s){
        System.out.println(s);
    }
    public static void print(char c[]){
        System.out.println(c);
    }
    public static void main(String[] args) throws IOException{
        //try{
        BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
        String input;
        Integer n;
        String h;
        h=in.readLine();
        n=Integer.parseInt(h);
        for(Integer i=0;i<n;i++){
            input = in.readLine();
            char c[]=new char[input.length()];
            c=input.toCharArray();
            //If input is 9
            if(c[0]=='9'&&input.length()==1){
                print("11");
            }
            //If input is other than 9
            else{
                //If input length is even
                if(input.length()%2==0){
                    for(int j=0,q=input.length()-1;j<(input.length()/2)&&q>=(input.length()/2);j++,q--){
                        c[q]=c[j];
                    }
                }
                //If input length is odd
                else{
                    for(int j=0,q=input.length()-1;j<=Math.round((input.length()/2))-1&&q>=Math.round((input.length()/2))-1;j++,q--){
                        c[q]=c[j];
                    }
                }
                    //Checking if new value is greater than old one
                BigInteger newval = new BigInteger(String.valueOf(c));
                    BigInteger oldval = new BigInteger(input);
                    if(newval.compareTo(oldval)==1){
                        print(c);
                    }
                    else{
                        //Length is even
                        if(input.length()%2==0){
                            Integer mid=(input.length()/2)-1;
                            for(Integer even=mid;even>=0;even--){
                                if(c[even]=='9'){
                                c[even]=(char)48;
                                if(even!=0)
                                if(c[even-1]!='9'){
                                    c[even-1]=(char)(Character.getNumericValue(c[even-1])+49);
                                    break;
                                }
                                }
                                else{
                                    c[even]=(char)(Character.getNumericValue(c[even])+49);
                                    break;
                                }
                            }
                            for(int j=0,q=input.length()-1;j<(input.length()/2)&&q>=(input.length()/2);j++,q--){
                                c[q]=c[j];
                            }
                            if(c[0]=='0'){
                                c[input.length()-1]='1';
                                System.out.print(1);
                            }
                            System.out.println(c);      
                        }
                        else{
                            Integer mid=input.length()/2;
                            for(Integer even=mid;even>=0;even--){
                                if(c[even]=='9'){
                                c[even]=(char)48;
                                if(even!=0)
                                if(c[even-1]!='9'){
                                    c[even-1]=(char)(Character.getNumericValue(c[even-1])+49);
                                    break;
                                }
                                }
                                else{
                                    c[even]=(char)(Character.getNumericValue(c[even])+49);
                                    break;
                                }
                            }
                            for(int j=0,q=input.length()-1;j<=Math.round((input.length()/2))-1&&q>=Math.round((input.length()/2))-1;j++,q--){
                                c[q]=c[j];
                            }
                            if(c[0]=='0'){
                                c[input.length()-1]='1';
                                System.out.print(1);
                            }
                            print(c);
                    }
                }
            }
        }
        in.close();
        //}catch(Exception e){}
    }
}

The answer is correct. But I keep on getting TLE.

Answer 1

I finally solved it:

1. I noticed that some steps are repeated for both cases where the length is even and odd with only the mid value changing.

   //If input length is even
               if(len%2==0){
                   mid=(len/2)-1;
                   left=mid;
                   right=mid+1;
               }
   //If input length is odd
               else{
                   mid=(len/2);
                   left=mid-1;
                   right=mid+1;
               }
   

2. Instead of copying values from the left half to right half, I checked whether the middle values are same and ignored them while decrementing the left value and incrementing the right value.

   while (left >= 0 && c[left] == c[right]){
                   left--;right++;
               }
   

3. The above step also discarded the need to convert the String to BigInteger for comparing. Instead by checking the final left and right values the comparison can be done.

   if ( left < 0 || c[left] > c[right])
                   System.out.println(c);
   

Refer to this GeeksForGeeks link for a clear idea.

I am not posting the final code as so it should not let you drift from your efforts. That feeling when it got accepted gave an immense pleasure and it was worth it.