title: A better algorithm to find the next palindrome of a number string
body: <p>Firstly here is the problem:</p>
  <p>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.</p>
  <p>Input: The first line contains integer t, the number of test cases. Integers K are given in the next t lines.</p>
  <p>Output: For each K, output the smallest palindrome larger than K.
  Example</p>
  <p>Input:</p>
  <blockquote>
  <p>2</p>
  <p>808</p>
  <p>2133</p>
  </blockquote>
  <p>Output:</p>
  <blockquote>
  <p>818</p>
  <p>2222</p>
  </blockquote>
  <p>Secondly here is my code:</p>
  <pre><code>// I know it is bad practice to not cater for erroneous input,
  // however for the purpose of the execise it is omitted
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Scanner;
  import java.lang.Exception;
  import java.math.BigInteger;
  
  public class Main
  {    
      public static void main(String [] args){   
          try{
              Main instance = new Main(); // create an instance to access non-static
                                          // variables
          
              // Use java.util.Scanner to scan the get the input and initialise the
              // variable
              Scanner sc=null;
  
              BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
  
              String input = &quot;&quot;;
  
              int numberOfTests = 0;
  
              String k; // declare any other variables here
              
              if((input = r.readLine()) != null){
                  sc = new Scanner(input);
                  numberOfTests = sc.nextInt();
              }
  
              for (int i = 0; i &lt; numberOfTests; i++){
                  if((input = r.readLine()) != null){
                      sc = new Scanner(input);
                      k=sc.next(); // initialise the remainder of the variables sc.next()
                      instance.palindrome(k);
                  } //if
              }// for
          }// try
  
          catch (Exception e)
          {
              e.printStackTrace();
          }
      }// main
  
      public void palindrome(String number){
  
          StringBuffer theNumber = new StringBuffer(number);
          int length = theNumber.length();
          int left, right, leftPos, rightPos;
          // if incresing a value to more than 9 the value to left (offset) need incrementing
          int offset, offsetPos;
          boolean offsetUpdated;
          // To update the string with new values
          String insert;
          boolean hasAltered = false;
  
          for(int i = 0; i &lt; length/2; i++){
              leftPos = i; 
              rightPos = (length-1) - i;
              offsetPos = rightPos -1; offsetUpdated = false;
              
              // set values at opposite indices and offset
              left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
              right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
              offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
  
              if(left != right){
                  // if r &gt; l then offest needs updating
                  if(right &gt; left){
                      // update and replace
                      right = left;
                      insert = Integer.toString(right);
  
                      theNumber.replace(rightPos, rightPos + 1, insert);
                  
                      offset++; if (offset == 10) offset = 0;
                      insert = Integer.toString(offset);
  
                      theNumber.replace(offsetPos, offsetPos + 1, insert);
                      offsetUpdated = true;
                 
                      // then we need to update the value to left again
                      while (offset == 0 &amp;&amp; offsetUpdated){ 
                          offsetPos--;
                          offset =
                              Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
                          offset++; if (offset == 10) offset = 0;
                          // replace
                          insert = Integer.toString(offset);
                          theNumber.replace(offsetPos, offsetPos + 1, insert);
                      }
                      // finally incase right and offset are the two middle values
                      left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
                      if (right != left){
                          right = left;
                          insert = Integer.toString(right);
                          theNumber.replace(rightPos, rightPos + 1, insert);
                      }
                  }// if r &gt; l
                  else
                      // update and replace
                      right = left;
                      insert = Integer.toString(right);
                      theNumber.replace(rightPos, rightPos + 1, insert);           
              }// if l != r
          }// for i
          System.out.println(theNumber.toString());
      }// palindrome
  }
  </code></pre>
  <p>Finally my explaination and question.</p>
  <pre><code>My code compares either end and then moves in
      if left and right are not equal
          if right is greater than left
              (increasing right past 9 should increase the digit
               to its left i.e 09 ---- &gt; 10) and continue to do
               so if require as for 89999, increasing the right
               most 9 makes the value 90000
          
               before updating my string we check that the right
               and left are equal, because in the middle e.g 78849887
               we set the 9 --&gt; 4 and increase 4 --&gt; 5, so we must cater for this.
  </code></pre>
  <p>The problem is from spoj.pl an online judge system. My code works for all the test  can provide but when I submit it, I get a time limit exceeded error and my answer is not accepted.</p>
  <p>Does anyone have any suggestions as to how I can improve my algorithm. While writing this question i thought that instead of my while (offset == 0 &amp;&amp; offsetUpdated) loop i could use a boolean to to make sure i increment the offset on my next [i] iteration. Confirmation of my chang or any suggestion would be appreciated, also let me know if i need to make my question clearer.</p>