Solution: Super Palindromes
Tags: algorithsm, javascript, java, python
Published: 2021-05-08 16:05:33

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/super-palindromes/discuss/1197697).*

---

#### [Leetcode Problem #906 (*Hard*): Super Palindromes](https://leetcode.com/problems/super-palindromes/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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]`.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|left = "4", right = "1000"
Output:|4
Explanation:|4, 9, 121, and 484 are superpalindromes.<br>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]`.
 - `left` is less than or equal to `right`.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The 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.

Starting 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.

Consider the small palindrome values found between **"1"** and **"9999999999999"**:
```
[1, 2, 3, 11, 22, 101, 111, 121, 202, 212, 1001, 1111, 2002, 10001, 10101,
 10201, 11011, 11111, 11211, 20002, 20102, 100001, 101101, 110011, 111111,
 200002, 1000001, 1001001, 1002001, 1010101, 1011101, 1012101, 1100011,
 1101011, 1102011, 1110111, 1111111, 2000002, 2001002]
```
Right 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.

Looking a little more closely at the valid numbers above, we can also notice a few more things:
 - A **2** can only exist on the edges of the value or the middle position of a value with an odd length.
 - If the edges are **2**s, then the only other variation is a **1** in the middle on odd length values.

Using 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.

In 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.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***Building Palindromes:***
```javascript
var superpalindromesInRange = function(left, right) {
    let ans = 9 >= left && 9 <= right ? 1 : 0

    const isPal = str => {
        for (let i = 0, j = str.length - 1; i < j; i++, j--)
            if (str.charAt(i) !== str.charAt(j)) return false
        return true
    }

    for (let dig = 1; dig < 10; dig++) {
        let isOdd = dig % 2 && dig !== 1,
            innerLen = (dig >> 1) - 1, innerLim = Math.max(1, 2 ** innerLen),
            midPos = dig >> 1, midLim = isOdd ? 3 : 1
        for (let edge = 1; edge < 3; edge++) {
            let pal = new Uint8Array(dig)
            pal[0] = edge, pal[dig-1] = edge
            if (edge === 2) innerLim = 1, midLim = Math.min(midLim, 2)
            for (let inner = 0; inner < innerLim; inner++) {
                if (inner > 0) {
                    let innerStr = inner.toString(2).padStart(innerLen, '0')
                    for (let i = 0; i < innerLen; i++)
                        pal[1+i] = innerStr[i], pal[dig-2-i] = innerStr[i]
                }
                for (let mid = 0; mid < midLim; mid++) {
                    if (isOdd) pal[midPos] = mid
                    let palin = ~~pal.join(""),
                        square = BigInt(palin) * BigInt(palin)
                    if (square > right) return ans
                    if (square >= left && isPal(square.toString())) ans++
                }
            }
        }
    }
    return ans
};
```

##### ***Base3 Iteration:***
```javascript
var superpalindromesInRange = function(left, right) {
    let ans = 9 >= left && 9 <= right ? 1 : 0
    
    const isPal = str => {
        for (let i = 0, j = str.length - 1; i < j; i++, j--)
            if (str.charAt(i) !== str.charAt(j)) return false
        return true
    }
    
    for (let i = 1; i < 19684; i++) {
        let num = i.toString(3)
        if (isPal(num)) {
            let square = BigInt(num) * BigInt(num)
            if (square > right) return ans
            if (square >= left && isPal(square.toString())) ans++
        }
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***Building Palindromes:***
```python
class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        ans = 1 if 9 >= int(left) and 9 <= int(right) else 0
        
        def isPal(s: str) -> bool:
            return s == s[::-1]
        
        for dig in range(1, 10):
            isOdd = dig % 2 and dig != 1
            innerLen = (dig >> 1) - 1
            innerLim = max(1, 2 ** innerLen)
            midPos = dig >> 1
            midLim = 3 if isOdd else 1
            for edge in range (1, 3):
                pal = [0] * dig
                pal[0], pal[-1] = edge, edge
                if edge == 2: innerLim, midLim = 1, min(midLim, 2)
                for inner in range(innerLim):
                    if inner > 0:
                        innerStr = list(bin(inner)[2:].zfill(innerLen))
                        pal[1:1+innerLen] = innerStr
                        pal[-innerLen-1:-1] = reversed(innerStr)
                    for mid in range(midLim):
                        if isOdd: pal[midPos] = mid
                        palin = int("".join([str(n) for n in pal]))
                        square = palin * palin
                        if square > int(right): return ans
                        if square >= int(left) and isPal(str(square)): ans += 1
        return ans
```

##### ***Base3 Iteration:***
```python
class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        ans = 1 if 9 >= int(left) and 9 <= int(right) else 0
        
        def isPal(s: str) -> bool:
            return s == s[::-1]
        
        def base3(n: int, num: str) -> str:
            if not n: return num
            n, r = divmod(n, 3)
            return base3(n, str(r) + num)
        
        for i in range(1, 19684):
            num = base3(i, "")
            if isPal(num):
                square = int(num) * int(num)
                if square > int(right): return ans
                if square >= int(left) and isPal(str(square)): ans += 1
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***Building Palindromes:***
```java
class Solution {
    public int superpalindromesInRange(String left, String right) {
        int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;
  
        for (int dig = 1; dig < 10; dig++) {
            boolean isOdd = dig % 2 > 0 && dig != 1;
            int innerLen = (dig >> 1) - 1,
                innerLim = Math.max(1, (int)Math.pow(2, innerLen)),
                midPos = dig >> 1, midLim = isOdd ? 3 : 1;
            for (int edge = 1; edge < 3; edge++) {
                char[] pal = new char[dig];
                Arrays.fill(pal, '0');
                pal[0] = (char)(edge + 48);
                pal[dig-1] = (char)(edge + 48);
                if (edge == 2) {
                    innerLim = 1;
                    midLim = Math.min(midLim, 2);
                }
                for (int inner = 0; inner < innerLim; inner++) {
                    if (inner > 0) {
                        String innerStr = Integer.toString(inner, 2);
                        while (innerStr.length() < innerLen)
                            innerStr = "0" + innerStr;
                        for (int i = 0; i < innerLen; i++) {
                            pal[1+i] = innerStr.charAt(i);
                            pal[dig-2-i] = innerStr.charAt(i);
                        }
                    }
                    for (int mid = 0; mid < midLim; mid++) {
                        if (isOdd) pal[midPos] = (char)(mid + 48);
                        String palin = new String(pal);
                        long square = Long.parseLong(palin) * Long.parseLong(palin);
                        if (square > Long.parseLong(right)) return ans;
                        if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;
                    }
                }
            }
        }
        return ans;
    }
    
    private boolean isPal(String str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--)
            if (str.charAt(i) != str.charAt(j)) return false;
        return true;
    }
}
```

##### ***Base3 Iteration:***
```java
class Solution {
    public int superpalindromesInRange(String left, String right) {
        int ans = 9 >= Long.parseLong(left) && 9 <= Long.parseLong(right) ? 1 : 0;
        for (int i = 1; i < 19684; i++) {
            String num = Integer.toString(i, 3);
            if (isPal(num)) {
                long square = Long.parseLong(num) * Long.parseLong(num);
                if (square > Long.parseLong(right)) return ans;
                if (square >= Long.parseLong(left) && isPal(Long.toString(square))) ans++;
            }
        }
        return ans;
    }
    
    private boolean isPal(String str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--)
            if (str.charAt(i) != str.charAt(j)) return false;
        return true;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***Building Palindromes:***
```c++
class Solution {
public:
    int superpalindromesInRange(string left, string right) {
        int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;
        for (int dig = 1; dig < 10; dig++) {
            bool isOdd = dig % 2 && dig != 1;
            int innerLen = (dig >> 1) - 1,
                innerLim = max(1, (int)pow(2, innerLen)),
                midPos = dig >> 1, midLim = isOdd ? 3 : 1;
            for (int edge = 1; edge < 3; edge++) {
                string pal(dig, '0');
                pal[0] = (char)(edge + 48);
                pal[dig-1] = (char)(edge + 48);
                if (edge == 2) innerLim = 1, midLim = min(midLim, 2);
                for (int inner = 0; inner < innerLim; inner++) {
                    if (inner > 0) {
                        string innerStr = bitset<3>(inner).to_string();
                        innerStr = innerStr.substr(3 - innerLen);
                        for (int i = 0; i < innerLen; i++) {
                            pal[1+i] = innerStr[i];
                            pal[dig-2-i] = innerStr[i];
                        }
                    }
                    for (int mid = 0; mid < midLim; mid++) {
                        if (isOdd) pal[midPos] = (char)(mid + 48);
                        long square = stol(pal) * stol(pal);
                        if (square > stol(right)) return ans;
                        if (square >= stol(left) && isPal(to_string(square))) ans++;
                    }
                }
            }
        }
        return ans;
    }
    
    bool isPal(string str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--)
            if (str[i] != str[j]) return false;
        return true;
    }
};
```

##### ***Base3 Iteration:***
```c++
class Solution {
public:
    int superpalindromesInRange(string left, string right) {
        int ans = 9 >= stol(left) && 9 <= stol(right) ? 1 : 0;
        for (int i = 1; i < 19684; i++) {
            string num = base3(i);
            if (isPal(num)) {
                long square = stol(num) * stol(num);
                if (square > stol(right)) return ans;
                if (square >= stol(left) && isPal(to_string(square))) ans++;
            }
        }
        return ans;
    }
    
    string base3(int n, string num="") {
        if (!n) return num;
        div_t divres = div(n, 3);
        return base3(divres.quot, (char)(divres.rem + 48) + num);
    }
    
    bool isPal(string str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--)
            if (str[i] != str[j]) return false;
        return true;
    }
};
```