This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #906 (Hard): Super Palindromes
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
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
leftandrightrepresented as strings, return the number of super-palindromes integers in the inclusive range[left, right].
Examples:
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 <= 18leftandrightconsist of only digits.leftandrightcannot have leading zeros.leftandrightrepresent integers in the range[1, 1018].leftis less than or equal toright.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
The first thing we should be able to realize about this problem is that it will be easier to start from the small palindrome and square it, rather than starting from the large palindrome and squarerooting it. This is especially useful because the constraint on the large palindrome goes up to 18 digits which means the small palindrome can only go up to 9 digits.
Starting with the smaller palindrome, we can easily create a function isPal() to test if a string is a palindrome, then use it to iteratively check for values that are palindromes and whose squares are also palindromes. This will result in a TLE before it can reach the constraint, but we can use it to find out some interesting information about the small palindromes.
Consider the small palindrome values found between "1" and "9999999999999":
[1, 2, 3, 11, 22, 101, 111, 121, 202, 212, 1001, 1111, 2002, 10001, 10101,
10201, 11011, 11111, 11211, 20002, 20102, 100001, 101101, 110011, 111111,
200002, 1000001, 1001001, 1002001, 1010101, 1011101, 1012101, 1100011,
1101011, 1102011, 1110111, 1111111, 2000002, 2001002]
Right away, we can notice that, with the exception of the 3, only the numbers 0, 1, & 2 are used in each value. We could, at this point, fairly easily write a function that would iterate through every base3 number from 1 to the maximum value of 19683 (3^9, since the small palindrome is limited to 9 digits) and check it the same way as before. This is a major drop from 1000000000 iterations to only 19683 iterations.
Looking a little more closely at the valid numbers above, we can also notice a few more things:
- A 2 can only exist on the edges of the value or the middle position of a value with an odd length.
- If the edges are 2s, then the only other variation is a 1 in the middle on odd length values.
Using these observations, we can modify our function to build strings matching these rules. As attempting to follow these rules will prevent the base3 shortcut, we'll have to build the strings in a more manual operation, but that also means that we can use the opportunity to ensure that we're only building palindromes, in order to further decrease the iteration count.
In fact, if we follow these rules, we'll only actually iterate through a maximum of 74 values, of which 70 are the valid numbers in the constrained limits.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
Building Palindromes:
var superpalindromesInRange = function(left, right) {
let ans = 9 >= left && 9 <= right ? 1 : 0
const isPal = str => {
for (let i = 0, j = str.length - 1; i < j; i++, j--)
if (str.charAt(i) !== str.charAt(j)) return false
return true
}
for (let dig = 1; dig < 10; dig++) {
let isOdd = dig % 2 && dig !== 1,
innerLen = (dig >> 1) - 1, innerLim = Math.max(1, 2 ** innerLen),
midPos = dig >> 1, midLim = isOdd ? 3 : 1
for (let edge = 1; edge < 3; edge++) {
let pal = new Uint8Array(dig)
pal[0] = edge, pal[dig-1] = edge
if (edge === 2) innerLim = 1, midLim = Math.min(midLim, 2)
for (let inner = 0; inner < innerLim; inner++) {
if (inner > 0) {
let innerStr = inner.toString(2).padStart(innerLen, '0')
for (let i = 0; i < innerLen; i++)
pal[1+i] = innerStr[i], pal[dig-2-i] = innerStr[i]
}
for (let mid = 0; mid < midLim; mid++) {
if (isOdd) pal[midPos] = mid
let palin = ~~pal.join(""),
square = BigInt(palin) * BigInt(palin)
if (square > right) return ans
if (square >= left && isPal(square.toString())) ans++
}
}
}
}
return ans
};
Base3 Iteration:
var superpalindromesInRange = function(left, right) {
let ans = 9 >= left && 9 <= right ? 1 : 0
const isPal = str => {
for (let i = 0, j = str.length - 1; i < j; i++, j--)
if (str.charAt(i) !== str.charAt(j)) return false
return true
}
for (let i = 1; i < 19684; i++) {
let num = i.toString(3)
if (isPal(num)) {
let square = BigInt(num) * BigInt(num)
if (square > right) return ans
if (square >= left && isPal(square.toString())) ans++
}
}
return ans
};
Python Code:
(Jump to: Problem Description || Solution Idea)
Building Palindromes:
class Solution:
def superpalindromesInRange(self, left: str, right: str) -> int:
ans = 1 if 9 >= int(left) and 9 <= int(right) else 0
def isPal(s: str) -> bool:
return s == s[::-1]
for dig in range(1, 10):
isOdd = dig % 2 and dig != 1
innerLen = (dig >> 1) - 1
innerLim = max(1, 2 ** innerLen)
midPos = dig >> 1
midLim = 3 if isOdd else 1
for edge in range (1, 3):
pal = [0] * dig
pal[0], pal[-1] = edge, edge
if edge == 2: innerLim, midLim = 1, min(midLim, 2)
for inner in range(innerLim):
if inner > 0:
innerStr = list(bin(inner)[2:].zfill(innerLen))
pal[1:1+innerLen] = innerStr
pal[-innerLen-1:-1] = reversed(innerStr)
for mid in range(midLim):
if isOdd: pal[midPos] = mid
palin = int("".join([str(n) for n in pal]))
square = palin * palin
if square > int(right): return ans
if square >= int(left) and isPal(str(square)): ans += 1
return ans
Base3 Iteration:
class Solution:
def superpalindromesInRange(self, left: str, right: str) -> int:
ans = 1 if 9 >= int(left) and 9 <= int(right) else 0
def isPal(s: str) -> bool:
return s == s[::-1]
def base3(n: int, num: str) -> str:
if not n: return num
n, r = divmod(n, 3)
return base3(n, str(r) + num)
for i in range(1, 19684):
num = base3(i, "")
if isPal(num):
square = int(num) * int(num)
if square > int(right): return ans
if square >= int(left) and isPal(str(square)): ans += 1
return ans
Java Code:
(Jump to: Problem Description || Solution Idea)
Building Palindromes:
class Solution {
public int superpalindromesInRange(String left, String right) {
int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;
for (int dig = 1; dig < 10; dig++) {
boolean isOdd = dig % 2 > 0 && dig != 1;
int innerLen = (dig >> 1) - 1,
innerLim = Math.max(1, (int)Math.pow(2, innerLen)),
midPos = dig >> 1, midLim = isOdd ? 3 : 1;
for (int edge = 1; edge < 3; edge++) {
char[] pal = new char[dig];
Arrays.fill(pal, '0');
pal[0] = (char)(edge + 48);
pal[dig-1] = (char)(edge + 48);
if (edge == 2) {
innerLim = 1;
midLim = Math.min(midLim, 2);
}
for (int inner = 0; inner < innerLim; inner++) {
if (inner > 0) {
String innerStr = Integer.toString(inner, 2);
while (innerStr.length() < innerLen)
innerStr = "0" + innerStr;
for (int i = 0; i < innerLen; i++) {
pal[1+i] = innerStr.charAt(i);
pal[dig-2-i] = innerStr.charAt(i);
}
}
for (int mid = 0; mid < midLim; mid++) {
if (isOdd) pal[midPos] = (char)(mid + 48);
String palin = new String(pal);
long square = Long.parseLong(palin) * Long.parseLong(palin);
if (square > Long.parseLong(right)) return ans;
if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;
}
}
}
}
return ans;
}
private boolean isPal(String str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str.charAt(i) != str.charAt(j)) return false;
return true;
}
}
Base3 Iteration:
class Solution {
public int superpalindromesInRange(String left, String right) {
int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;
for (int i = 1; i < 19684; i++) {
String num = Integer.toString(i, 3);
if (isPal(num)) {
long square = Long.parseLong(num) * Long.parseLong(num);
if (square > Long.parseLong(right)) return ans;
if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;
}
}
return ans;
}
private boolean isPal(String str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str.charAt(i) != str.charAt(j)) return false;
return true;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
Building Palindromes:
class Solution {
public:
int superpalindromesInRange(string left, string right) {
int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;
for (int dig = 1; dig < 10; dig++) {
bool isOdd = dig % 2 && dig != 1;
int innerLen = (dig >> 1) - 1,
innerLim = max(1, (int)pow(2, innerLen)),
midPos = dig >> 1, midLim = isOdd ? 3 : 1;
for (int edge = 1; edge < 3; edge++) {
string pal(dig, '0');
pal[0] = (char)(edge + 48);
pal[dig-1] = (char)(edge + 48);
if (edge == 2) innerLim = 1, midLim = min(midLim, 2);
for (int inner = 0; inner < innerLim; inner++) {
if (inner > 0) {
string innerStr = bitset<3>(inner).to_string();
innerStr = innerStr.substr(3 - innerLen);
for (int i = 0; i < innerLen; i++) {
pal[1+i] = innerStr[i];
pal[dig-2-i] = innerStr[i];
}
}
for (int mid = 0; mid < midLim; mid++) {
if (isOdd) pal[midPos] = (char)(mid + 48);
long square = stol(pal) * stol(pal);
if (square > stol(right)) return ans;
if (square >= stol(left) && isPal(to_string(square))) ans++;
}
}
}
}
return ans;
}
bool isPal(string str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str[i] != str[j]) return false;
return true;
}
};
Base3 Iteration:
class Solution {
public:
int superpalindromesInRange(string left, string right) {
int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;
for (int i = 1; i < 19684; i++) {
string num = base3(i);
if (isPal(num)) {
long square = stol(num) * stol(num);
if (square > stol(right)) return ans;
if (square >= stol(left) && isPal(to_string(square))) ans++;
}
}
return ans;
}
string base3(int n, string num="") {
if (!n) return num;
div_t divres = div(n, 3);
return base3(divres.quot, (char)(divres.rem + 48) + num);
}
bool isPal(string str) {
for (int i = 0, j = str.length() - 1; i < j; i++, j--)
if (str[i] != str[j]) return false;
return true;
}
};
Top comments (0)