Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.
Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].
Example 1:
Input: left = "4", right = "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.
Example 2:
Input: left = "1", right = "2" Output: 1
Constraints:
1 <= left.length, right.length <= 18left and right consist of only digits.left and right cannot have leading zeros.left and right represent integers in the range [1, 1018 - 1].left is less than or equal to right.This approach involves generating palindromes within a certain range, then squaring these palindromes and checking if the result is also a palindrome and within the given range. We generate palindromic numbers using digit manipulation and check each step if they meet the conditions.
This Python code defines a function called superpalindromes_in_range that takes in two strings left and right as its parameters. The function checks all numbers formed by odd and even length palindromes up to a limit (specified by a magic number, here 10**5) to see if their squares lie within the specified range and are themselves palindromes. If so, the function increments a counter which is returned as the result.
C++
Time Complexity: O(Magic * log(M)) where M is the limit (in this case, MAGIC) for generating palindromes.
Space Complexity: O(1), since we only use a fixed amount of extra space.
In this method, instead of generating palindromes up to a specific length, we iteratively construct them by appending mirrored sections. The main difference from the first approach is the construction and early exit mechanism based on the calculated square exceeding the right bound.
This JavaScript implementation follows the same algorithm of iteratively building palindromes using mirrored string operations and checks whether the resulting squares fall within the range and are palindromic. It makes use of BigInt for handling large numbers due to JavaScript's number size limits.
Java
Time Complexity: O(Magic * log(M)) where M is the limit (here MAGIC) for generating palindromes.
Space Complexity: O(1) because of the absence of additional dynamic storage.
| Approach | Complexity |
|---|---|
| Brute Force Generation of Palindromes | Time Complexity: O(Magic * log(M)) where M is the limit (in this case, MAGIC) for generating palindromes. Space Complexity: O(1), since we only use a fixed amount of extra space. |
| Iterative Palindrome Construction | Time Complexity: O(Magic * log(M)) where M is the limit (here MAGIC) for generating palindromes. Space Complexity: O(1) because of the absence of additional dynamic storage. |
Longest Palindromic Substring - Python - Leetcode 5 • NeetCode • 629,128 views views
Watch 9 more video solutions →Practice Super Palindromes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor