Sponsored
Sponsored
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.
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.
1def is_palindrome(x):
2 s = str(x)
3 return s == s[::-1]
4
5
6def superpalindromes_in_range(left: str, right: str) -> int:
7 L = int(left)
8 R = int(right)
9 MAGIC = 10**5 # Generate palindromes up to this range
10 count = 0
11
12 # odd length palindrome
13 for k in range(1, MAGIC):
14 s = str(k)
15 t = s + s[-2::-1] # create odd-length palindrome
16 v = int(t) ** 2
17 if v > R:
18 break
19 if v >= L and is_palindrome(v):
20 count += 1
21
22 # even length palindrome
23 for k in range(1, MAGIC):
24 s = str(k)
25 t = s + s[::-1] # create even-length palindrome
26 v = int(t) ** 2
27 if v > R:
28 break
29 if v >= L and is_palindrome(v):
30 count += 1
31
32 return countThis 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.
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.
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.
1function isPalindrome(x) {
2 let
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.