Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/906.html
906. Super Palindromes (Hard)
Let's say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.
Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].
Example 1:
Input: L = "4", R = "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.
Note:
1 <= len(L) <= 181 <= len(R) <= 18LandRare strings representing integers in the range[1, 10^18).int(L) <= int(R)
Companies:
Google
Related Topics:
Math
Solution 1.
// OJ: https://leetcode.com/problems/super-palindromes/
// Time: O(W^(1/4)*logW)
// Space: O(logW)
// Ref: https://leetcode.com/problems/super-palindromes/solution/
typedef unsigned long long ULL;
class Solution {
private:
bool isPalindrome(ULL n) {
ULL r = 0, num = n;
while (n) {
r = r * 10 + n % 10;
n /= 10;
}
return r == num;
}
public:
int superpalindromesInRange(string L, string R) {
ULL i = 1, ans = 0, nl = stoull(L), nr = stoull(R), MAGIC = 100000;
for (int k = 1; k < MAGIC; ++k) {
string s = to_string(k);
for (int i = s.size() - 2; i >= 0; --i) s += s[i];
ULL n = stoull(s);
n *= n;
if (n > nr) break;
if (n >= nl && isPalindrome(n)) ++ans;
}
for (int k = 1; k < MAGIC; ++k) {
string s = to_string(k);
for (int i = s.size() - 1; i >= 0; --i) s += s[i];
ULL n = stoull(s);
n *= n;
if (n > nr) break;
if (n >= nl && isPalindrome(n)) ++ans;
}
return ans;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/super-palindromes/
// Time: O(1)
// Space: O(1)
// Ref: https://leetcode.com/problems/super-palindromes/discuss/170728/no-more-this-type-questions-for-contest!
typedef unsigned long long ULL;
class Solution {
public:
int superpalindromesInRange(string L, string R) {
vector<ULL> v{
1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004 ,404090404, 10000200001l, 10221412201l, 12102420121l, 12345654321l, 40000800004l , 1000002000001l, 1002003002001l, 1004006004001l, 1020304030201l, 1022325232201l, 1024348434201l, 1210024200121l, 1212225222121l, 1214428244121l, 1232346432321l, 1234567654321l, 4000008000004l, 4004009004004l, 100000020000001l, 100220141022001l, 102012040210201l, 102234363432201l, 121000242000121l, 121242363242121l, 123212464212321l, 123456787654321l, 400000080000004l, 10000000200000001l, 10002000300020001l, 10004000600040001l, 10020210401202001l, 10022212521222001l, 10024214841242001l, 10201020402010201l, 10203040504030201l, 10205060806050201l, 10221432623412201l, 10223454745432201l, 12100002420000121l, 12102202520220121l, 12104402820440121l, 12122232623222121l, 12124434743442121l, 12321024642012321l, 12323244744232321l, 12343456865434321l, 12345678987654321l, 40000000800000004l, 40004000900040004l
};
return upper_bound(v.begin(), v.end(), stoull(R)) - lower_bound(v.begin(), v.end(), stoull(L));
}
};
-
class Solution { public int superpalindromesInRange(String L, String R) { long squareLow = Long.parseLong(L), squareHigh = Long.parseLong(R); long low = (long) Math.ceil(Math.sqrt(squareLow)); long high = (long) Math.floor(Math.sqrt(squareHigh)); int count = 0; for (int i = 1; i < 100000; i++) { long palindrome = getOddLengthPalindrome(i); if (palindrome < low) continue; else if (palindrome > high) break; else { long square = palindrome * palindrome; if (isPalindrome(square)) count++; } } for (int i = 1; i < 100000; i++) { long palindrome = getEvenLengthPalindrome(i); if (palindrome < low) continue; else if (palindrome > high) break; else { long square = palindrome * palindrome; if (isPalindrome(square)) count++; } } return count; } public long getOddLengthPalindrome(int num) { StringBuffer sb = new StringBuffer(String.valueOf(num)); int length = sb.length(); for (int i = length - 2; i >= 0; i--) sb.append(sb.charAt(i)); return Long.parseLong(sb.toString()); } public long getEvenLengthPalindrome(int num) { StringBuffer sb = new StringBuffer(String.valueOf(num)); int length = sb.length(); for (int i = length - 1; i >= 0; i--) sb.append(sb.charAt(i)); return Long.parseLong(sb.toString()); } public boolean isPalindrome(long num) { char[] array = String.valueOf(num).toCharArray(); int left = 0, right = array.length - 1; while (left < right) { if (array[left] != array[right]) return false; left++; right--; } return true; } } -
// OJ: https://leetcode.com/problems/super-palindromes/ // Time: O(W^(1/4)*logW) // Space: O(logW) class Solution { long getPalindrome(long half, bool odd) { long ans = half; if (odd) half /= 10; for (; half; half /= 10) ans = ans * 10 + half % 10; return ans; } bool isPalindrome(long n) { long tmp = n, r = 0; for (; tmp; tmp /= 10) r = r * 10 + tmp % 10; return r == n; } public: int superpalindromesInRange(string left, string right) { long L = stoll(left), R = stoll(right), ans = 0; for (int len = 1; true; ++len) { for (long half = pow(10L, (len - 1) / 2), end = half * 10; half < end; ++half) { long pal = getPalindrome(half, len % 2), sq = pal * pal; if (sq < L) continue; if (sq > R) return ans; ans += isPalindrome(sq); } } return 0; } }; -
class Solution: def superpalindromesInRange(self, L, R): """ :type L: str :type R: str :rtype: int """ que = collections.deque(["11", "22"]) candi = set() while que: size = len(que) for _ in range(size): p = que.popleft() candi.add(p) if int(p) ** 2 > int(R): continue for j in ["0", "1", "2"]: q = (p[:len(p)//2] + j + p[len(p)//2:]) que.append(q) candi.add("1") candi.add("2") candi.add("3") res = 0 for cand in candi: if int(L) <= int(cand) ** 2 <= int(R) and self.isPalindromes(int(cand) ** 2): res += 1 return res def isPalindromes(self, s): s = str(s) N = len(s) for l in range(1, N // 2): if s[l] != s[N - 1 - l]: return False return True