Palindromic Password

This problem gives us a series of 6 digit numbers and asks us what the nearest polynomial is.

A naive brute force solution is to just iterate up and down to the next palindrome. This gives 1000 (N) * 1,000,000 (search space), which is too large. We see however, that for any grouping of the largest 3 most significant digits, there are 3 least significant digits that will make a palindrome. This means that there must be some palindrome at worst within 1000 of us. This limits our search to at max 2000 numbers. 2 million is fast enough.

We can optimize further. We can precompute every palindrome less than 1 million. There are 1000 of them. This brings the runtime down by half.

If we are especially clever, we can directly calculate the palindrome. We know it must either be within our grouping of 1000 (same first 3 digits), or in the next group of 1000 or the previous one. We can directly generate the palindromes in each of those three groupings and return the minimum one.