Find Next Palindrome Number

Question: Given a number, find the next smallest palindrome larger than the number. For example if the number is 125, next smallest palindrome is 131.

Solution 1:The brute-force approach is to increment the number until we get a palindrome. So at every iteration we check whether the new number is palindrome or not. This is the most straightforward non-optimal solution.

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

/**  * Mirror the number such that lower half digits same as higher half of digits  * For example, the mirror of 65432 is 65456  *  * @param n  * @return  */ int mirror(int n) {     String num = String.valueOf(n);     char[] arr = num.toCharArray();     int mid = arr.length/2;     int i= (arr.length%2==0)?mid:mid+1;     // copy higher half of digits to lower half     while(i<arr.length) {         arr[i]=arr[mid-1];         mid--;         i++;     }     num=String.valueOf(arr);     return Integer.valueOf(num); }   int incrementFromMiddle(int n) {     String num = String.valueOf(n);     char[] arr = num.toCharArray();     int midpoint = arr.length/2;     int currPoint=arr.length%2==0?midpoint-1:midpoint;     boolean found = false;            while (currPoint >= 0 && !found) {         char c = arr[currPoint];         char inc;         if (c == '9') {           inc = '0';         }         else {           inc = (char) (c + 1);           found = true;         }         arr[currPoint] = inc;         if (!found) {           currPoint--;         }       }              if (!found) {         // we have fallen off the start of the string         // example 999 has become 009. Add a one on to give: 1009         final char[] newarr = new char[arr.length + 1];         newarr[0] = '1';         System.arraycopy(arr, 0, newarr, 1, arr.length);         num = new String(newarr);         return Integer.valueOf(num);       }       else {           num = new String(arr);           return Integer.valueOf(num);                  } } // Give next palindrome from a given number which might not be palindrome int nextPalindrome(int n) {     int mirror = mirror(n);     if(mirror <= n) {         mirror = mirror(incrementFromMiddle(n));            }     return mirror; }