906. Super Palindromes

Description

Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.

Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].

 

Example 1:

Input: left = "4", right = "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.

Example 2:

Input: left = "1", right = "2"
Output: 1

 

Constraints:

• 1 <= left.length, right.length <= 18
• left and right consist of only digits.
• left and right cannot have leading zeros.
• left and right represent integers in the range [1, 1018 - 1].
• left is less than or equal to right.

 

Solutions

Solution: Enumeration

• Time complexity: O(10^{right.length/2} * right.length)
• Space complexity: O(right.length/2)

 

JavaScript

/**
 * @param {string} left
 * @param {string} right
 * @return {number}
 */
const superpalindromesInRange = function (left, right) {
  const MAX_LENGTH = Math.ceil(right.length / 2);
  let result = 0;

  const isPalindrome = num => {
    let left = 0;
    let right = num.length - 1;

    while (left < right) {
      if (num[left] !== num[right]) return false;
      left += 1;
      right -= 1;
    }
    return true;
  };

  const createPalindrome = current => {
    if (current.length > MAX_LENGTH) return;
    if (current && current[0] !== '0') {
      const num = BigInt(current) ** 2n;

      if (num > BigInt(right)) return;
      if (num >= BigInt(left) && isPalindrome(`${num}`)) result += 1;
    }

    for (let num = 0; num <= 9; num++) {
      createPalindrome(`${num}${current}${num}`);
    }
  };

  createPalindrome('');

  for (let num = 0; num <= 9; num++) {
    createPalindrome(`${num}`);
  }
  return result;
};