# 906. Super Palindromes

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public: int superpalindromesInRange(string left, string right) { int ans = 0; long long l = stoll(left); long long r = stoll(right); for (long long i = sqrt(l); i * i <= r;) { long long palindrome = nextPalindrome(i); long long squared = palindrome * palindrome; if (squared <= r && isPalindrome(squared)) ++ans; i = palindrome + 1; } return ans; } private: long long nextPalindrome(int num) { const string s = to_string(num); const int n = s.length(); string half = s.substr(0, (n + 1) / 2); string reversedHalf = reversed(half.substr(0, n / 2)); const long long candidate = stoll(half + reversedHalf); if (candidate >= num) return candidate; half = to_string(stoll(half) + 1); reversedHalf = reversed(half.substr(0, n / 2)); return stoll(half + reversedHalf); } string reversed(const string& s) { return {rbegin(s), rend(s)}; } bool isPalindrome(long long num) { const string s = to_string(num); int l = 0; int r = s.length() - 1; while (l < r) if (s[l++] != s[r--]) return false; return true; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public int superpalindromesInRange(String left, String right) { int ans = 0; Long l = Long.valueOf(left); Long r = Long.valueOf(right); for (long i = (long) Math.sqrt(l); i * i <= r;) { long palindrome = nextPalindrome(i); long squared = palindrome * palindrome; if (squared <= r && isPalindrome(squared)) ++ans; i = palindrome + 1; } return ans; } private long nextPalindrome(long num) { final String s = String.valueOf(num); final int n = s.length(); String half = s.substring(0, (n + 1) / 2); String reversedHalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString(); final long candidate = Long.valueOf(half + reversedHalf); if (candidate >= num) return candidate; half = String.valueOf(Long.valueOf(half) + 1); reversedHalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString(); return Long.valueOf(half + reversedHalf); } private boolean isPalindrome(long num) { final String s = String.valueOf(num); int l = 0; int r = s.length() - 1; while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false; return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution: def superpalindromesInRange(self, left: str, right: str) -> int: def nextPalindrome(num: int) -> int: s = str(num) n = len(s) half = s[0:(n + 1) // 2] reversedHalf = half[:n // 2][::-1] candidate = int(half + reversedHalf) if candidate >= num: return candidate half = str(int(half) + 1) reversedHalf = half[:n // 2][::-1] return int(half + reversedHalf) def isPalindrome(num: int) -> bool: s = str(num) l = 0 r = len(s) - 1 while l < r: if s[l] != s[r]: return False l += 1 r -= 1 return True ans = 0 l = int(left) r = int(right) i = int(sqrt(l)) while i * i <= r: palindrome = nextPalindrome(i) squared = palindrome**2 if squared <= r and isPalindrome(squared): ans += 1 i = palindrome + 1 return ans