## How is it work

In my solution, there are 5 situations:

011single digitlike 1~910 based numberlike 10, 100, 1000 etc.the others

The most complicated one is **situation 5**, cause there would be **3** close palindromes of 1 number:

palindrome by itselfpalindrome a little bigger than itselfpalindrome a little smaller than itself

So, the value `offset`

is to generate them. Then, we get palindrome with the offset number. And finally, we compare three of them, and get the closest and smaller one.

## Complexity

The time O is `3 * n/2 + 3`

= **n**

## Code

```
public String nearestPalindromic(String n) {
long num = Long.valueOf(n);
if (num == 0) return "1";
if (num == 11) return "9";
if (num <= 10 || Math.log10(num)%1==0) return num - 1 + "";
long exp = n.length() - (n.length() - 1) / 2 - 1;
long offset = (long) Math.pow(10, exp);
return min(num, palindry(n), palindry(num + offset + ""), palindry(num - offset + ""));
}
//choose the closest number away from target
private String min(long target, long s1, long s2, long s3) {
long[] array = { s1, s2, s3 };
long[] distance = new long[3];
for (int i = 0; i < array.length; i++) {
distance[i] = Math.abs(target - array[i]);
//exclude itself
if (distance[i] == 0) distance[i] = Long.MAX_VALUE;
}
int minIndex = distance[0] > distance[1] ? 1 : 0;
return array[distance[2] > distance[minIndex] ? minIndex : 2] + "";
}
//get a normal palindrome number
private long palindry(String n) {
char[] c = n.toCharArray();
for (int i = 0; i < c.length / 2; i++) {
c[c.length - i - 1] = c[i];
}
return new Long(new String(c));
}
```