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.
1#include <iostream>
2#include <string>
3#include <cmath>
4
5bool isPalindrome(long x) {
6 std::string s = std::to_string(x);
7 int n = s.size();
8 for (int i = 0; i < n / 2; ++i) {
9 if (s[i] != s[n - i - 1]) return false;
10 }
11 return true;
12}
13
14int superpalindromesInRange(std::string left, std::string right) {
15 long L = std::stol(left), R = std::stol(right);
16 const long MAGIC = 100000; // Generate palindromes up to this range
17 int count = 0;
18
19 // odd length palindromes
20 for (int k = 1; k < MAGIC; ++k) {
21 std::string s = std::to_string(k);
22 std::string t = s + std::string(s.rbegin() + 1, s.rend());
23 long v = std::stol(t);
24 v *= v;
25 if (v > R) break;
26 if (v >= L && isPalindrome(v)) {
27 count++;
28 }
29 }
30
31 // even length palindromes
32 for (int k = 1; k < MAGIC; ++k) {
33 std::string s = std::to_string(k);
34 std::string t = s + std::string(s.rbegin(), s.rend());
35 long v = std::stol(t);
36 v *= v;
37 if (v > R) break;
38 if (v >= L && isPalindrome(v)) {
39 count++;
40 }
41 }
42
43 return count;
44}This C++ solution works similarly to the Python approach. It checks if numbers created through both odd and even digit palindromes, when squared, are within the given range and are themselves palindromes. This solution makes use of string manipulations and basic arithmetic to form palindromes, square them, and validate the conditions.
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.
1public class SuperPalindromes {
2 public
The Java solution constructs palindromes by concisely appending mirrored parts of the string, akin to the methods in other language solutions. The range is checked by transforming these palindromes into numbers and ensuring their square values are in range and themselves palindromes.