1364. How Many Palindromic Numbers
Count the integers from 1 to n that read the same forwards and backwards.
n = 9 -> 9 every single digit
n = 10 -> 9 10 is not one
n = 11 -> 10
n = 100 -> 18
Checking every value is O(n) and too slow at 10^9.
Build the palindromes instead of testing for them. A palindrome is completely
determined by its FIRST HALF: choose the half and the rest is forced by
mirroring. So for each length, run through the possible halves and count the
ones whose palindrome does not exceed n:
for each length L from 1 to the number of digits of n:
half = (L + 1) / 2
for h from 10^(half-1) to 10^half - 1:
build the palindrome from h
count it if it is at most n
There are about sqrt(n) palindromes below n in total, so this is roughly
10^5 steps at the maximum rather than 10^9.
The mirroring differs by parity, and that is where the errors live. For an odd
length the middle digit is not repeated, so the mirrored part drops its first
character. Getting that wrong shows up immediately at n = 11, and the tests
include both parities on either side of a boundary.
Constraints - `1 ≤ n ≤ 1000000000`
Input
One line containing the integer n.
Output
Print how many integers from 1 to n are palindromic.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.