Solution


Approach 1: Mathematical

Intuition

Say is a superpalindrome.

Because is a palindrome, the first half of the digits in determine up to two possibilities. We can iterate through these digits: let be the first half of the digits in . For example, if , then or . Each possibility has either an odd or an even number of digits in .

Notice because , , and (concatenation), where is reversed (and also possibly truncated by one digit); so that , our magic constant.

Algorithm

For each , let's create the associated palindrome , and check whether is a palindrome.

We should handle the odd and even possibilities separately, as we would like to break early so as not to do extra work.

To check whether an integer is a palindrome, we could check whether it is equal to its reverse. To create the reverse of an integer, we can do it digit by digit.

Complexity Analysis

  • Time Complexity: , where is our upper limit for . The term comes from checking whether each candidate is the root of a palindrome.

  • Space Complexity: , the space used to create the candidate palindrome.


Analysis written by: @awice.