LeetCode 906: Super Palindromes Solution

Master LeetCode problem 906 (Super Palindromes), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

906. Super Palindromes

Hard

Math String Enumeration

Problem Explanation

Explanation

To solve this problem, we need to generate and check all possible super-palindromes within the given range [left, right]. We can do this by checking all palindromes within the range of sqrt(left) and sqrt(right) and then verifying if their square is a palindrome as well. We will need to implement functions to check if a number is a palindrome and to generate palindromes.

Generate all palindromes within the range [sqrt(left), sqrt(right)].
Check if the square of each palindrome is also a palindrome.
Count the number of super-palindromes found.

Time complexity: O(sqrt(n) * log(n)), where n is the difference between left and right. Space complexity: O(log(n))

Solution Code

class Solution {
    public int superpalindromesInRange(String left, String right) {
        long L = Long.parseLong(left);
        long R = Long.parseLong(right);
        int MAGIC = 100000;
        int ans = 0;

        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.parseLong(sb.toString());
            v *= v;
            if (v > R) {
                break;
            }
            if (v >= L && isPalindrome(v)) {
                ans++;
            }
        }

        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.parseLong(sb.toString());
            v *= v;
            if (v > R) {
                break;
            }
            if (v >= L && isPalindrome(v)) {
                ans++;
            }
        }

        return ans;
    }

    private boolean isPalindrome(long x) {
        return x == Long.parseLong(new StringBuilder(Long.toString(x)).reverse().toString());
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 906 (Super Palindromes)?

This page provides optimized solutions for LeetCode problem 906 (Super Palindromes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 906 (Super Palindromes)?

The time complexity for LeetCode 906 (Super Palindromes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 906 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 906 in Java, C++, or Python.

Back to LeetCode Solutions