LeetCode 906 - Super Palindromes

https://leetcode.com/problems/super-palindromes/

Let's say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.

Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].

Example 1:

Input: L = "4", R = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Note:

1. 1 <= len(L) <= 18
2. 1 <= len(R) <= 18
3. L and R are strings representing integers in the range [1, 10^18).
4. int(L) <= int(R)

http://hehejun.blogspot.com/2018/09/leetcodesuper-palindromes.html
这道题R的最大值可以到达10^18，所以我们只需要验证[1, 10^9]的回文，既然要求是回文，长度又可以砍一半，所以我们需要验证的是：

• [1, 9999]范围中的数为前一半，长度为偶数的回文
• [1, 99999]范围中的数为前一半，个位数为中心，长度为奇数的回文

因为10^9肯定不是回文，所以我们不需要管。这样可以保证我们遍历[1, 999999999]中的所有回文，我们依次check这些回文是不是满足要求。时间复杂度O(M^0.25 * log M)，M为R的最大值

https://leetcode.com/articles/super-palindromes/

• Time Complexity: $O(W^{\frac{1}{4}} * \log W)$∗logW), where $W = 10^{18}$ is our upper limit for $R$. The $\log W$ term comes from checking whether each candidate is the root of a palindrome.
• Space Complexity: $O(\log W)$, the space used to create the candidate palindrome. 

  public int superpalindromesInRange(String sL, String sR) {

    long L = Long.valueOf(sL);

    long R = Long.valueOf(sR);

    int MAGIC = 100000;

    int ans = 0;

    // count odd length;

    for (int k = 1; k < MAGIC; ++k) {

      StringBuilder sb = new StringBuilder(Integer.toString(k));

      for (int i = sb.length() - 2; i >= 0; --i)

        sb.append(sb.charAt(i));

      long v = Long.valueOf(sb.toString());

      v *= v;

      if (v > R)

        break;

      if (v >= L && isPalindrome(v))

        ans++;

    }

    // count even length;

    for (int k = 1; k < MAGIC; ++k) {

      StringBuilder sb = new StringBuilder(Integer.toString(k));

      for (int i = sb.length() - 1; i >= 0; --i)

        sb.append(sb.charAt(i));

      long v = Long.valueOf(sb.toString());

      v *= v;

      if (v > R)

        break;

      if (v >= L && isPalindrome(v))

        ans++;

    }

    return ans;

  }

  public boolean isPalindrome(long x) {

    return x == reverse(x);

  }

  public long reverse(long x) {

    long ans = 0;

    while (x > 0) {

      ans = 10 * ans + x % 10;

      x /= 10;

    }

    return ans;

  }

https://leetcode.com/problems/super-palindromes/discuss/170774/Java-building-the-next-palindrome

    public int superpalindromesInRange(String L, String R) {
        Long l = Long.valueOf(L), r = Long.valueOf(R);
        int result = 0;
        for (long i = (long)Math.sqrt(l); i * i <= r;) {
            long p = nextP(i);
            if (p * p <= r && isP(p * p)) {
                result++;
            }
            i = p + 1;
        }
        return result;
    }
    
    private long nextP(long l) {
        String s = "" + l;
        int len = s.length();
        List<Long> cands = new LinkedList<>();
        cands.add((long)Math.pow(10, len) - 1);
        String half = s.substring(0, (len + 1) / 2);
        String nextHalf = "" + (Long.valueOf(half) + 1);
        String reverse = new StringBuilder(half.substring(0, len / 2)).reverse().toString();
        String nextReverse = new StringBuilder(nextHalf.substring(0, len / 2)).reverse().toString();
        cands.add(Long.valueOf(half + reverse));
        cands.add(Long.valueOf(nextHalf + nextReverse));
        long result = Long.MAX_VALUE;
        for (long i : cands) {
            if (i >= l) {
                result = Math.min(result, i);
            }
        }
        return result;
    }
    
    private boolean isP(long l) {
        String s = "" + l;
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }

X. Precompute
https://leetcode.com/problems/super-palindromes/discuss/170748/Just-Run-a-brute-force-locally-and-print-table!
Just Run a brute-force locally and print table!
https://leetcode.com/problems/super-palindromes/discuss/170728/no-more-this-type-questions-for-contest!

vector<uint64_t> value {
    0, 1, 4, 9, 121, 484, 676, 10201, 12321, 14641, 40804, 44944, 69696, 94249, 698896, 1002001, 1234321, 
    4008004, 5221225, 6948496, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 
    404090404, 522808225, 617323716, 942060249, 10000200001, 10221412201, 12102420121, 12345654321, 
    40000800004, 637832238736, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 
    1024348434201, 1086078706801, 1210024200121, 1212225222121, 1214428244121, 1230127210321, 1232346432321, 
    1234567654321, 1615108015161, 4000008000004, 4004009004004, 4051154511504, 5265533355625, 9420645460249, 
    100000020000001, 100220141022001, 102012040210201, 102234363432201, 121000242000121, 121242363242121, 
    123212464212321, 123456787654321, 123862676268321, 144678292876441, 165551171155561, 400000080000004, 
    900075181570009, 4099923883299904, 10000000200000001, 10002000300020001, 10004000600040001, 10020210401202001, 
    10022212521222001, 10024214841242001, 10201020402010201, 10203040504030201, 10205060806050201, 
    10221432623412201, 10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121, 
    12120030703002121, 12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321, 
    12341234943214321, 12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004, 94206450305460249,
};

class Solution {
public:
    int superpalindromesInRange(string L, string R) {
        auto l = lower_bound(value.begin(), value.end(), stoull(L));
        auto r = upper_bound(value.begin(), value.end(), stoull(R));
        int res = 0;
        for (;l != r; ++l) {
            int64_t v = *l;
            int64_t root = round(sqrt(v));
            string s1 = to_string(root);
            string s2 = s1;
            reverse(s2.begin(), s2.end());
            if (s2 == s1) ++res;
        }
        return res;
    }