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.