LeetCode 906: Super Palindromes

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

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) <= 18\$$
• $$\1 <= len(R) <= 18\$$
• L and R are strings representing integers in the range [1, 10^18).
• int(L) <= int(R)

Inputs

"4"
"1000"

"10"
"99999199999"

"1"
"999999999999999999"


Outputs

4
23
70


Code

#include <cstdint>
#include <cmath>
#include <string>
#include <math.h>
#include <queue>
#include <utility>

struct Solution {
static std::int_fast32_t superpalindromesInRange(const std::string L, const std::string R) {
const long double lo_bound = sqrtl(stol(L));
const long double hi_bound = sqrtl(stol(R));
std::int_fast32_t superpalindromes = lo_bound <= 3 && 3 <= hi_bound;
std::queue<std::pair<long, std::int_fast32_t>> queue;
queue.push({1, 1});
queue.push({2, 1});

while (true) {
const auto curr = queue.front();
const long num = curr.first;
const std::int_fast32_t length = curr.second;
queue.pop();

if (num > hi_bound) {
break;
}

long W = powl(10, -~length / 2);

if (num >= lo_bound) {
superpalindromes += is_palindrome(num * num);
}

const long right = num % W;
const long left = num - (length & 1 ? num % (W / 10) : right);

if (length & 1) {
queue.push({10 * left + right, -~length});

} else {
for (std::int_fast8_t d = 0; d < 3; ++d) {
queue.push({10 * left + d * W + right, -~length});
}
}
}

return superpalindromes;
}

private:
static bool is_palindrome(const long num) {
if (!num) {
return true;
}

if (!num % 10) {
return false;
}

long left = num;
long right = 0;

while (left >= right) {
if (left == right || left / 10 == right) {
return true;
}

right = 10 * right + (left % 10);
left /= 10;
}

return false;
}

};



References

• The code wastes quite a few cycles rejecting palindromes less than lo_bound. It is not hard to find the smallest palindrome above lo_bound, and start from there.

If you are not comfortable constructing such palindrome, consider lifting the lead-in into the separate loop:

    long num = 1;
while (num < lo_bound) {
num = make_next_palindrome(queue);
}

• The entire business around queue is very non-obvious, and it takes a great mental effort to realize that it iterates palindromes. I recommend to factor this logic out into a class of its own, along the lines of

class palindrome_iterator {
std::queue<...> queue;
// length, W, etc as necessary
public:
palindrome_iterator(long start_num);
long next();
};


This way the main loop is streamlined into

    palindrome_iterator p_i(lo_bound);
for (long num = p_i.next(); num < hi_bound; num = p_i.next()) {
superpalindromes += is_palindrome(num * num);
}


An additional (and possibly more important) benefit of such refactoring is that it enables unit testing of palindrome generation logic (which really sreams to be unit tested).

• I strongly advise against -~length trick. length + 1 is much more clear, and for sure not slower.