How to optimize the following java code i had written to generate next palindrome number

Question

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;
import javax.swing.event.AncestorEvent;


public class NextPalindrome {
    public static void main(String args[])
    {
        Scanner console = new Scanner(System.in);
        ArrayList<BigInteger> inArr = new ArrayList<BigInteger>();
        int tc = console.nextInt();
        for(int x =0 ;x<tc;x++){
            BigInteger num = console.nextBigInteger();

            num = num.add(BigInteger.valueOf(1));
            inArr.add(num);
        }
        for(int y =0 ;y<tc;y++)
        {

            while(!checkPal(inArr.get(y))){
                BigInteger temp = inArr.get(y);
                temp = inArr.get(y).add(BigInteger.valueOf(1));
                inArr.set(y, temp);
            }
            System.out.println(inArr.get(y));
        }
    }
    static boolean checkPal(BigInteger num){
        String str = num.toString();
        char[] charStr = str.toCharArray();
        //System.out.println(charStr);
        boolean isPal= true;
        int first =0;
        int last = str.length()-1;
        for(int i = 0; i<str.length();i++){
            if(charStr[first] == charStr[last])
            {
                first++;
                last--;
                continue;
            }else
            {
                isPal = false;
                break;
            }
        }
        return isPal;

    }

}

This piece of code which i have written works fine for smaller to mid sized inputs but if i give a bigger number like any random bigger number it says time limit exceeded.Can any one give inputs regarding this.

Why do you store the numbers in an array ? Just read them from console as you need them. — Florent Bayle, Jan 15 '15 at 09:41
Thsts because i define the number of inputs and then based on that i take the number of testcases — poseidon_rishi, Jan 15 '15 at 11:42
That doesn't change what I said, you can still read them from the console as you need them. — Florent Bayle, Jan 15 '15 at 11:46

score 3 · Answer 1 · answered Jan 15 '15 at 09:42

A palidrome is when the second half is a reflection of the first half.

All you need do is to take the first half of the number, increment it and reverse the digits of the first half. e.g. say you have.

326856897845875634

take the first half

326856897

increment it (after checking that generating a palindrome for this number is not greater)

326856898

and as it is an even length number reverse the first half.

326856898898658623

if it is an odd length number you don't need to reverse the middle digit.

Rather than brute force which will take increasing amounts of time, every digit you add will take ten times longer. Using the approach is proportional to the number of digits.

Also the code should be about half the size.

The first half is `999999` and the number is 12 digits long if you increment it you get `1000000` and the new length should be 13. i.e. the second half will be a reflection with the middle digit the same. — Peter Lawrey, Jan 15 '15 at 13:14

How to optimize the following java code i had written to generate next palindrome number

1 Answers1