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 <= len(L) <= 18
1 <= len(R) <= 18
L and R are strings representing integers in the range [1, 10^18).
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

var ps [2 * 100000]int64

func init() {
	for i := 1; i <= 100000; i++ {
		s := strconv.Itoa(i)
		t1 := reverseString(s)
		t2 := reverseString(s[:len(s)-1])
		ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
		ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
	}
}

func reverseString(s string) string {
	cs := []rune(s)
	for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
		cs[i], cs[j] = cs[j], cs[i]
	}
	return string(cs)
}

func superpalindromesInRange(left string, right string) (ans int) {
	l, _ := strconv.ParseInt(left, 10, 64)
	r, _ := strconv.ParseInt(right, 10, 64)
	isPalindrome := func(x int64) bool {
		var y int64
		for t := x; t > 0; t /= 10 {
			y = y*10 + int64(t%10)
		}
		return x == y
	}
	for _, p := range ps {
		x := p * p
		if x >= l && x <= r && isPalindrome(x) {
			ans++
		}
	}
	return
}

const ps = Array(2e5).fill(0);

const init = (() => {
    for (let i = 1; i <= 1e5; ++i) {
        const s: string = i.toString();
        const t1: string = s.split('').reverse().join('');
        const t2: string = s.slice(0, -1).split('').reverse().join('');
        ps[2 * i - 2] = parseInt(s + t1, 10);
        ps[2 * i - 1] = parseInt(s + t2, 10);
    }
})();

function superpalindromesInRange(left: string, right: string): number {
    const l = BigInt(left);
    const r = BigInt(right);
    const isPalindrome = (x: bigint): boolean => {
        const s: string = x.toString();
        return s === s.split('').reverse().join('');
    };
    let ans = 0;
    for (const p of ps) {
        const x = BigInt(p) * BigInt(p);
        if (x >= l && x <= r && isPalindrome(x)) {
            ++ans;
        }
    }
    return ans;
}

906 - Super Palindromes

906. Super Palindromes (Hard)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

906. Super Palindromes (Hard)

Solution 1.

All Problems

All Solutions