<p>Let&#39;s say a positive integer is a <strong>super-palindrome</strong> if it is a palindrome, and it is also the square of a palindrome.</p>

<p>Given two positive integers <code>left</code> and <code>right</code> represented as strings, return <em>the number of <strong>super-palindromes</strong> integers in the inclusive range</em> <code>[left, right]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> left = &quot;4&quot;, right = &quot;1000&quot;
<strong>Output:</strong> 4
<strong>Explanation</strong>: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> left = &quot;1&quot;, right = &quot;2&quot;
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= left.length, right.length &lt;= 18</code></li>
	<li><code>left</code> and <code>right</code> consist of only digits.</li>
	<li><code>left</code> and <code>right</code> cannot have leading zeros.</li>
	<li><code>left</code> and <code>right</code> represent integers in the range <code>[1, 10<sup>18</sup> - 1]</code>.</li>
	<li><code>left</code> is less than or equal to <code>right</code>.</li>
</ul>

class Solution {
public:
    unsigned long reverseNum(unsigned long n){
        if (n<10) return n;
        unsigned long digit, rev = 0;
        unsigned long num = n;
        
        do
        {
            digit = num % 10;
            rev = ((rev << 3) + (rev<<1)) + digit;
            num = num/10;
        } while (num != 0);

        return rev;
    }
    bool isPalindrome(unsigned long n){
        unsigned long rev = reverseNum(n);
        return n==rev;
    }

    int superpalindromesInRange(string left, string right) {
        
        unsigned long leftVal = std::stol(left);
        unsigned long rightVal = std::stol(right);

        int superPalindromes = 0;

        // if R^2 < 10^18
        // R < 10^9
        // R is Palindromic, so P (repeating set of R - if P=1234, R=1234321 or 12344321) is less than 10^5

        for (unsigned long i=1; i<100000; i++){
            unsigned long pal1, pal2 = 0;
            if (i< (unsigned long) 10){
                pal1 = i;
                pal2 = (i<<3)+(i<<1)+i; // 11i
            }
            else if (i< (unsigned long) 100){
                pal1 = (i<<6)+(i<<5)+(i<<2)+reverseNum(i);
                pal2 = (i<<3)+(i<<1)+reverseNum(i)%10;
            }
            else if (i< (unsigned long) 1000){
                pal1 = (i<<10)-(i<<4)-(i<<3)+reverseNum(i);
                pal2 = (i<<6)+(i<<5)+(i<<2)+reverseNum(i)%100;
            }
            else if (i< (unsigned long) 10000){
                pal1 = i*10000+reverseNum(i);
                pal2 = (i<<10)-(i<<4)-(i<<3)+reverseNum(i)%1000;
            }
            else if (i< (unsigned long) 100000){
                pal1 = i*100000+reverseNum(i);
                pal2 = i*10000+reverseNum(i)%10000;
            }
            pal1 = pal1*pal1;
            pal2 = pal2*pal2;
            if (pal1>=leftVal && pal1 <= rightVal && isPalindrome(pal1)){
                std::cout << "pal1 accepted: " << pal1 << " on index " << i << std::endl;
                superPalindromes++;
            }
            if (pal2>=leftVal && pal2 <= rightVal && isPalindrome(pal2)){
                std::cout << "pal2 accepted: " << pal2 << " on index " << i << std::endl;
                superPalindromes++;
            }
        }

        return superPalindromes;
    }
};
7300