Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/906.html

906. Super Palindromes (Hard)

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)

 

Companies:
Google

Related Topics:
Math

Solution 1.

  • class Solution {
        public int superpalindromesInRange(String L, String R) {
            long squareLow = Long.parseLong(L), squareHigh = Long.parseLong(R);
            long low = (long) Math.ceil(Math.sqrt(squareLow));
            long high = (long) Math.floor(Math.sqrt(squareHigh));
            int count = 0;
            for (int i = 1; i < 100000; i++) {
                long palindrome = getOddLengthPalindrome(i);
                if (palindrome < low)
                    continue;
                else if (palindrome > high)
                    break;
                else {
                    long square = palindrome * palindrome;
                    if (isPalindrome(square))
                        count++;
                }
            }
            for (int i = 1; i < 100000; i++) {
                long palindrome = getEvenLengthPalindrome(i);
                if (palindrome < low)
                    continue;
                else if (palindrome > high)
                    break;
                else {
                    long square = palindrome * palindrome;
                    if (isPalindrome(square))
                        count++;
                }
            }
            return count;
        }
    
        public long getOddLengthPalindrome(int num) {
            StringBuffer sb = new StringBuffer(String.valueOf(num));
            int length = sb.length();
            for (int i = length - 2; i >= 0; i--)
                sb.append(sb.charAt(i));
            return Long.parseLong(sb.toString());
        }
    
        public long getEvenLengthPalindrome(int num) {
            StringBuffer sb = new StringBuffer(String.valueOf(num));
            int length = sb.length();
            for (int i = length - 1; i >= 0; i--)
                sb.append(sb.charAt(i));
            return Long.parseLong(sb.toString());
        }
    
        public boolean isPalindrome(long num) {
            char[] array = String.valueOf(num).toCharArray();
            int left = 0, right = array.length - 1;
            while (left < right) {
                if (array[left] != array[right])
                    return false;
                left++;
                right--;
            }
            return true;
        }
    }
    
  • // OJ: https://leetcode.com/problems/super-palindromes/
    // Time: O(W^(1/4)*logW)
    // Space: O(logW)
    class Solution {
        long getPalindrome(long half, bool odd) {
            long ans = half;
            if (odd) half /= 10;
            for (; half; half /= 10) ans = ans * 10 + half % 10;
            return ans;
        }
        bool isPalindrome(long n) {
            long tmp = n, r = 0;
            for (; tmp; tmp /= 10) r = r * 10 + tmp % 10;
            return r == n;
        }
    public:
        int superpalindromesInRange(string left, string right) {
            long L = stoll(left), R = stoll(right), ans = 0;
            for (int len = 1; true; ++len) {
                for (long half = pow(10L, (len - 1) / 2), end = half * 10; half < end; ++half) {
                    long pal = getPalindrome(half, len % 2), sq = pal * pal;
                    if (sq < L) continue;
                    if (sq > R) return ans;
                    ans += isPalindrome(sq);
                }
            }
            return 0;
        }
    };
    
  • class Solution:
        def superpalindromesInRange(self, L, R):
            """
            :type L: str
            :type R: str
            :rtype: int
            """
            que = collections.deque(["11", "22"])
            candi = set()
            while que:
                size = len(que)
                for _ in range(size):
                    p = que.popleft()
                    candi.add(p)
                    if int(p) ** 2 > int(R):
                        continue
                    for j in ["0", "1", "2"]:
                        q = (p[:len(p)//2] + j + p[len(p)//2:])
                        que.append(q)
            candi.add("1")
            candi.add("2")
            candi.add("3")
            res = 0
            for cand in candi:
                if int(L) <= int(cand) ** 2 <= int(R) and self.isPalindromes(int(cand) ** 2):
                    res += 1
            return res
                    
                
        def isPalindromes(self, s):
            s = str(s)
            N = len(s)
            for l in range(1, N // 2):
                if s[l] != s[N - 1 - l]:
                    return False
            return True
    

All Problems

All Solutions