LeetCode 906: Super Palindromes

Question

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

• Problem

• Discuss

• Solution

Answer 1

• 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.