*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nThe first thing we should be able to realize about this problem is that it will be easier to start from the small palindrome and square it, rather than starting from the large palindrome and squarerooting it. This is especially useful because the constraint on the large palindrome goes up to **18** digits which means the small palindrome can only go up to **9** digits.\n\nStarting with the smaller palindrome, we can easily create a function **isPal()** to test if a string is a palindrome, then use it to iteratively check for values that are palindromes and whose squares are also palindromes. This will result in a **TLE** before it can reach the constraint, but we can use it to find out some interesting information about the small palindromes.\n\nConsider the small palindrome values found between **"1"** and **"9999999999999"**:\n```\n[1, 2, 3, 11, 22, 101, 111, 121, 202, 212, 1001, 1111, 2002, 10001, 10101,\n 10201, 11011, 11111, 11211, 20002, 20102, 100001, 101101, 110011, 111111,\n 200002, 1000001, 1001001, 1002001, 1010101, 1011101, 1012101, 1100011,\n 1101011, 1102011, 1110111, 1111111, 2000002, 2001002]\n```\nRight away, we can notice that, with the exception of the **3**, only the numbers **0**, **1**, & **2** are used in each value. We could, at this point, fairly easily write a function that would iterate through every **base3** number from **1** to the maximum value of **19683** (**3^9**, since the small palindrome is limited to **9** digits) and check it the same way as before. This is a major drop from **1000000000** iterations to only **19683** iterations.\n\nLooking a little more closely at the valid numbers above, we can also notice a few more things:\n - A **2** can only exist on the edges of the value or the middle position of a value with an odd length.\n - If the edges are **2**s, then the only other variation is a **1** in the middle on odd length values.\n\nUsing these observations, we can modify our function to build strings matching these rules. As attempting to follow these rules will prevent the **base3** shortcut, we\'ll have to build the strings in a more manual operation, but that also means that we can use the opportunity to ensure that we\'re only building palindromes, in order to further decrease the iteration count.\n\nIn fact, if we follow these rules, we\'ll only actually iterate through a maximum of **74** values, of which **70** are the valid numbers in the constrained limits.\n\n---\n\n#### ***Javascript Code:***\n\n##### ***Building Palindromes:***\n\nThe best result for the code below is **60ms / 38.2MB** (beats 100% / 100%).\n```javascript\nvar superpalindromesInRange = function(left, right) {\n let ans = 9 >= left && 9 <= right ? 1 : 0\n\n const isPal = str => {\n for (let i = 0, j = str.length - 1; i < j; i++, j--)\n if (str.charAt(i) !== str.charAt(j)) return false\n return true\n }\n\n for (let dig = 1; dig < 10; dig++) {\n let isOdd = dig % 2 && dig !== 1,\n innerLen = (dig >> 1) - 1, innerLim = Math.max(1, 2 ** innerLen),\n midPos = dig >> 1, midLim = isOdd ? 3 : 1\n for (let edge = 1; edge < 3; edge++) {\n let pal = new Uint8Array(dig)\n pal[0] = edge, pal[dig-1] = edge\n if (edge === 2) innerLim = 1, midLim = Math.min(midLim, 2)\n for (let inner = 0; inner < innerLim; inner++) {\n if (inner > 0) {\n let innerStr = inner.toString(2).padStart(innerLen, \'0\')\n for (let i = 0; i < innerLen; i++)\n pal[1+i] = innerStr[i], pal[dig-2-i] = innerStr[i]\n }\n for (let mid = 0; mid < midLim; mid++) {\n if (isOdd) pal[midPos] = mid\n let palin = ~~pal.join(""),\n square = BigInt(palin) * BigInt(palin)\n if (square > right) return ans\n if (square >= left && isPal(square.toString())) ans++\n }\n }\n }\n }\n return ans\n};\n```\n\n##### ***Base3 Iteration:***\n\nThe best result for the code below is **116ms / 42.1MB** (beats 100% / 100%).\n```javascript\nvar superpalindromesInRange = function(left, right) {\n let ans = 9 >= left && 9 <= right ? 1 : 0\n \n const isPal = str => {\n for (let i = 0, j = str.length - 1; i < j; i++, j--)\n if (str.charAt(i) !== str.charAt(j)) return false\n return true\n }\n \n for (let i = 1; i < 19684; i++) {\n let num = i.toString(3)\n if (isPal(num)) {\n let square = BigInt(num) * BigInt(num)\n if (square > right) return ans\n if (square >= left && isPal(square.toString())) ans++\n }\n }\n return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n\n##### ***Building Palindromes:***\n\nThe best result for the code below is **24ms / 14.1MB** (beats 100% / 94%).\n```python\nclass Solution:\n def superpalindromesInRange(self, left: str, right: str) -> int:\n ans = 1 if 9 >= int(left) and 9 <= int(right) else 0\n \n def isPal(s: str) -> bool:\n return s == s[::-1]\n \n for dig in range(1, 10):\n isOdd = dig % 2 and dig != 1\n innerLen = (dig >> 1) - 1\n innerLim = max(1, 2 ** innerLen)\n midPos = dig >> 1\n midLim = 3 if isOdd else 1\n for edge in range (1, 3):\n pal = [0] * dig\n pal[0], pal[-1] = edge, edge\n if edge == 2: innerLim, midLim = 1, min(midLim, 2)\n for inner in range(innerLim):\n if inner > 0:\n innerStr = list(bin(inner)[2:].zfill(innerLen))\n pal[1:1+innerLen] = innerStr\n pal[-innerLen-1:-1] = reversed(innerStr)\n for mid in range(midLim):\n if isOdd: pal[midPos] = mid\n palin = int("".join([str(n) for n in pal]))\n square = palin * palin\n if square > int(right): return ans\n if square >= int(left) and isPal(str(square)): ans += 1\n return ans\n```\n\n##### ***Base3 Iteration:***\n\nThe best result for the code below is **372ms / 14.0MB** (beats 95% / 100%).\n```python\nclass Solution:\n def superpalindromesInRange(self, left: str, right: str) -> int:\n ans = 1 if 9 >= int(left) and 9 <= int(right) else 0\n \n def isPal(s: str) -> bool:\n return s == s[::-1]\n \n def base3(n: int, num: str) -> str:\n if not n: return num\n n, r = divmod(n, 3)\n return base3(n, str(r) + num)\n \n for i in range(1, 19684):\n num = base3(i, "")\n if isPal(num):\n square = int(num) * int(num)\n if square > int(right): return ans\n if square >= int(left) and isPal(str(square)): ans += 1\n return ans\n```\n\n---\n\n#### ***Java Code:***\n\n##### ***Building Palindromes:***\n\nThe best result for the code below is **2ms / 36.8MB** (beats 91% / 96%).\n```java\nclass Solution {\n public int superpalindromesInRange(String left, String right) {\n int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;\n \n for (int dig = 1; dig < 10; dig++) {\n boolean isOdd = dig % 2 > 0 && dig != 1;\n int innerLen = (dig >> 1) - 1,\n innerLim = Math.max(1, (int)Math.pow(2, innerLen)),\n midPos = dig >> 1, midLim = isOdd ? 3 : 1;\n for (int edge = 1; edge < 3; edge++) {\n char[] pal = new char[dig];\n Arrays.fill(pal, \'0\');\n pal[0] = (char)(edge + 48);\n pal[dig-1] = (char)(edge + 48);\n if (edge == 2) {\n innerLim = 1;\n midLim = Math.min(midLim, 2);\n }\n for (int inner = 0; inner < innerLim; inner++) {\n if (inner > 0) {\n String innerStr = Integer.toString(inner, 2);\n while (innerStr.length() < innerLen)\n innerStr = "0" + innerStr;\n for (int i = 0; i < innerLen; i++) {\n pal[1+i] = innerStr.charAt(i);\n pal[dig-2-i] = innerStr.charAt(i);\n }\n }\n for (int mid = 0; mid < midLim; mid++) {\n if (isOdd) pal[midPos] = (char)(mid + 48);\n String palin = new String(pal);\n long square = Long.parseLong(palin) * Long.parseLong(palin);\n if (square > Long.parseLong(right)) return ans;\n if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;\n }\n }\n }\n }\n return ans;\n }\n \n private boolean isPal(String str) {\n for (int i = 0, j = str.length() - 1; i < j; i++, j--)\n if (str.charAt(i) != str.charAt(j)) return false;\n return true;\n }\n}\n```\n\n##### ***Base3 Iteration:***\n\nThe best result for the code below is **14ms / 39.0MB** (beats 91% / 81%).\n```java\nclass Solution {\n public int superpalindromesInRange(String left, String right) {\n int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;\n for (int i = 1; i < 19684; i++) {\n String num = Integer.toString(i, 3);\n if (isPal(num)) {\n long square = Long.parseLong(num) * Long.parseLong(num);\n if (square > Long.parseLong(right)) return ans;\n if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;\n }\n }\n return ans;\n }\n \n private boolean isPal(String str) {\n for (int i = 0, j = str.length() - 1; i < j; i++, j--)\n if (str.charAt(i) != str.charAt(j)) return false;\n return true;\n }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\n##### ***Building Palindromes:***\n\nThe best result for the code below is **0ms / 5.9MB** (beats 100% / 98%).\n```c++\nclass Solution {\npublic:\n int superpalindromesInRange(string left, string right) {\n int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;\n for (int dig = 1; dig < 10; dig++) {\n bool isOdd = dig % 2 && dig != 1;\n int innerLen = (dig >> 1) - 1,\n innerLim = max(1, (int)pow(2, innerLen)),\n midPos = dig >> 1, midLim = isOdd ? 3 : 1;\n for (int edge = 1; edge < 3; edge++) {\n string pal(dig, \'0\');\n pal[0] = (char)(edge + 48);\n pal[dig-1] = (char)(edge + 48);\n if (edge == 2) innerLim = 1, midLim = min(midLim, 2);\n for (int inner = 0; inner < innerLim; inner++) {\n if (inner > 0) {\n string innerStr = bitset<3>(inner).to_string();\n innerStr = innerStr.substr(3 - innerLen);\n for (int i = 0; i < innerLen; i++) {\n pal[1+i] = innerStr[i];\n pal[dig-2-i] = innerStr[i];\n }\n }\n for (int mid = 0; mid < midLim; mid++) {\n if (isOdd) pal[midPos] = (char)(mid + 48);\n long square = stol(pal) * stol(pal);\n if (square > stol(right)) return ans;\n if (square >= stol(left) && isPal(to_string(square))) ans++;\n }\n }\n }\n }\n return ans;\n }\n \n bool isPal(string str) {\n for (int i = 0, j = str.length() - 1; i < j; i++, j--)\n if (str[i] != str[j]) return false;\n return true;\n }\n};\n```\n\n##### ***Base3 Iteration:***\n\nThe best result for the code below is **44ms / 5.9MB** (beats 90% / 100%).\n```c++\nclass Solution {\npublic:\n int superpalindromesInRange(string left, string right) {\n int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;\n for (int i = 1; i < 19684; i++) {\n string num = base3(i);\n if (isPal(num)) {\n long square = stol(num) * stol(num);\n if (square > stol(right)) return ans;\n if (square >= stol(left) && isPal(to_string(square))) ans++;\n }\n }\n return ans;\n }\n \n string base3(int n, string num="") {\n if (!n) return num;\n div_t divres = div(n, 3);\n return base3(divres.quot, (char)(divres.rem + 48) + num);\n }\n \n bool isPal(string str) {\n for (int i = 0, j = str.length() - 1; i < j; i++, j--)\n if (str[i] != str[j]) return false;\n return true;\n }\n};\n```

Super Palindromes

Problem Description

Problem Description

Answer Panel