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.