Mirror Squares in a Range

Hard

Call a positive integer a mirror square if it is a palindrome (it reads the same in both directions) and is also the square of a palindrome. You are given two strings low and high holding positive integers. Return how many mirror squares lie in the range [low, high], inclusive. The numbers go up to 10¹⁸, so you cannot simply check each one.

Example 1

low="1", high="500" → 5

The matches are 1 = 1², 4 = 2², 9 = 3², 121 = 11² and 484 = 22². 676 = 26² is a palindrome, but 26 is not, and it lies outside the range anyway.

Example 2

low="10", high="100" → 0

No palindrome squared lands between 10 and 100 as a palindrome.

Example 3

low="10000", high="50000" → 5

Constraints

low and high consist of digits and have no leading zeros
1 ≤ low ≤ high ≤ 10¹⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math String Enumeration

Similar problems

Nearest Short Hex Color Easy Erase Digits Until It Divides by 25 Medium Even Vowel and Consonant Pieces Medium Plus-Minus Calculator With Brackets Hard Amount in Words Hard

Input

low="1", high="500"

Expected

Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.