Description

Submission

class Solution {
    typedef long long ll;
    // offset = 0 or 1
    string createPalindrome(string s, int offset = 0) {
        reverse_copy(s.begin(), s.end() - offset, back_inserter(s));
        return s;
    }

    bool isPalindrome(ll n) {
        string s = to_string(n);
        int len = s.length();
        for(int i = 0; i < len; ++i) {
            if(s[i] != s[len-1-i]) return false;
        }
        return true;
    }
public:
    int superpalindromesInRange(string left, string right) {
        int len1 = left.length() / 4, len2 = right.length() / 4 + 1;
        ll llLeft = stoll(left);
        ll llRight = stoll(right);

        int ret = 0;
        for(int i = pow(10, len1); i < pow(10, len2); ++i) {
            ll t0 = stoll(createPalindrome(to_string(i)));
            ll t1 = stoll(createPalindrome(to_string(i), 1));

            if(t0 <= 1e9) {
                ll p0 = t0 * t0;
                if(p0 >= llLeft && p0 <= llRight) {
                    if(isPalindrome(p0)) ++ret;
                }
            }
            if(t1 <= 1e9) {
                ll p1 = t1 * t1;
                if(p1 >= llLeft && p1 <= llRight) {
                    if(isPalindrome(p1)) ++ret;
                }    
            }

        }

        return ret;
    }
};

// N ~ 1e18
// approach 1(impossible):
// palindrome length: sqrt(1e18) = 1e9
// palindrome half length: sqrt(1e9)
// square of a number: O(sqrt(1e18)) = O(1e9): impossible
// O(N*sqrt(N))

// approach 2:
// palindrome length: sqrt(1e18) = 1e9
// palindrome half length: sqrt(1e9), square it and check if it's a palindrome
// O(sqrt(sqrt(N))*log(N))