1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.