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

vnp · Accepted Answer · 2020-07-20 23:54:14Z

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.

Stack Exchange Network

LeetCode 906: Super Palindromes

Problem

Example 1:

Inputs

Outputs

Code

References

1 Answer 1

You must log in to answer this question.

Hot Network Questions

LeetCode 906: Super Palindromes

Problem

Example 1:

Inputs

Outputs

Code

References

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions