# Strictly Palindromic Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/strictly-palindromic-number)
Canonical: https://scaleengineer.com/dsa/problems/strictly-palindromic-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
---
## Problem
An integer `n` is **strictly palindromic** if, for **every** base `b` between `2` and `n - 2` (**inclusive**), the string representation of the integer `n` in base `b` is **palindromic**.

Given an integer `n`, return `true` _if_ `n` _is **strictly palindromic** and_ `false` _otherwise_.

A string is **palindromic** if it reads the same forward and backward.

**Example 1:**

**Input:** n = 9
**Output:** false
**Explanation:** In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.

**Example 2:**

**Input:** n = 4
**Output:** false
**Explanation:** We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.

**Constraints:**

* `4 <= n <= 105`

# Approaches
## Brute Force Simulation
This approach directly implements the logic described in the problem statement. It systematically checks every base `b` in the range `[2, n - 2]`. For each base, it converts the number `n` to its representation in that base and then verifies if the resulting string is a palindrome. If any check fails, it immediately determines that `n` is not strictly palindromic.
**Time:** O(n * log n). The outer loop runs `n - 3` times. Inside the loop, converting `n` to a string in base `b` takes `O(log_b(n))` time, and checking if it's a palindrome also takes `O(log_b(n))`. Therefore, the total complexity is approximately `O(n * log n)`. · **Space:** O(log n). The space required is dominated by storing the string representation of `n` in a given base. The number of digits in base `b` is proportional to `log_b(n)`, which simplifies to `O(log n)`.
**Pros:** It is a straightforward and intuitive implementation of the problem definition.; The logic is easy to follow and debug.
**Cons:** This approach is very slow and will likely result in a 'Time Limit Exceeded' error for larger values of `n` due to its `O(n * log n)` complexity.; It fails to leverage the mathematical properties of the problem, leading to a lot of unnecessary computation.
### Explanation
The core of this method is a loop that runs from `b = 2` to `n - 2`. In each iteration, we perform two main tasks: number base conversion and palindrome checking.

First, we convert `n` to base `b`. A common way to do this is to build the string representation. For example, using `Integer.toString(n, b)` in Java simplifies this step. 

Second, we check if this new string is a palindrome. A simple and efficient way to do this is with two pointers. One pointer (`left`) starts at the beginning of the string, and the other (`right`) starts at the end. We compare the characters at `left` and `right`. If they are ever different, the string is not a palindrome. If they are the same, we move the pointers one step closer to the center (`left++`, `right--`) and repeat. The process continues until the pointers meet or cross.

If we find any base `b` for which the representation of `n` is not a palindrome, we can stop and return `false`. If the loop finishes, it means all representations were palindromic, and we would return `true`.

```java
class Solution {
    public boolean isStrictlyPalindromic(int n) {
        for (int b = 2; b <= n - 2; b++) {
            String baseBRepresentation = Integer.toString(n, b);
            if (!isPalindrome(baseBRepresentation)) {
                return false;
            }
        }
        return true;
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Create a loop that iterates through each base `b` from `2` to `n - 2`.
- Inside the loop, for each base `b`, convert the integer `n` into its string representation.
  - This can be done by repeatedly taking the modulus `n % b` to get the least significant digit and then updating `n` with `n / b` until `n` becomes 0.
  - Collect these digits to form a string.
- Check if the generated string is a palindrome.
  - Use a two-pointer approach, one at the start and one at the end of the string, moving inwards and comparing characters.
- If the string is not a palindrome for any base `b`, the number `n` is not strictly palindromic, so we can immediately return `false`.
- If the loop completes without returning, it means `n` is palindromic in all tested bases, so we return `true`.

## Constant Time Solution via Mathematical Insight
This highly efficient approach is based on a key mathematical observation. Instead of checking all bases, we can find a single base that disproves the condition for all `n` in the given range. By examining the representation of `n` in base `n - 2`, we can show that it's never a palindrome, allowing us to solve the problem in constant time.
**Time:** O(1). The solution consists of a single return statement and does not depend on the value of `n`. · **Space:** O(1). The solution uses no extra space that scales with the input `n`.
**Pros:** Extremely efficient, with constant time and space complexity.; Provides a definitive answer for the entire range of constraints without any iteration.
**Cons:** The solution relies on a specific mathematical insight or 'trick', which might not be immediately obvious.; It doesn't demonstrate the ability to write a general-purpose algorithm for the problem as stated, but rather exploits a loophole in the definition for the given constraints.
### Explanation
A number `n` is strictly palindromic only if its representation is a palindrome in *all* bases from `2` to `n - 2`. This means if we find even one base in this range for which the representation is *not* a palindrome, the condition fails, and the number is not strictly palindromic.

Let's pick a strategic base to test: `b = n - 2`. This base is always included in the range for `n >= 4`.

Now, let's find the representation of `n` in base `b = n - 2`.
We can express `n` in terms of `n - 2` as follows:
`n = (n - 2) + 2 = 1 * (n - 2)^1 + 2 * (n - 2)^0`

This equation shows that the representation of `n` in base `n - 2` consists of two digits: `1` followed by `2`. The resulting string is "12". This representation is valid as long as the digits are less than the base, i.e., `2 < n - 2`, which is true for `n > 4`.

The string "12" is not a palindrome. Therefore, for any `n > 4`, the number will fail the palindrome check in base `n - 2` and is thus not strictly palindromic.

For the remaining case, `n = 4`, the range of bases is just `b = 2`. The representation of `4` in base `2` is `100`, which is not a palindrome.

Since the condition fails for `n = 4` and for all `n > 4`, we can conclude that for any `n >= 4`, the answer is always `false`.

```java
class Solution {
    public boolean isStrictlyPalindromic(int n) {
        // For any integer n >= 4, let's consider the base b = n - 2.
        // The representation of n in base (n - 2) is "12".
        // n = 1 * (n - 2) + 2.
        // Since "12" is not a palindrome, n cannot be strictly palindromic.
        // This holds for n > 4. For n = 4, we check base 2. 4 in base 2 is "100", not a palindrome.
        // Thus, for the given constraints 4 <= n <= 10^5, the answer is always false.
        return false;
    }
}
```
### Algorithm
- Analyze the definition of a strictly palindromic number. It must be palindromic in *every* base `b` from `2` to `n - 2`.
- Realize that if we can find just one base `b` where `n` is not palindromic, we can prove that no number `n` (within the constraints) is strictly palindromic.
- Consider the specific base `b = n - 2`.
- Convert `n` to base `n - 2`. The division `n / (n - 2)` gives a quotient of `1` and a remainder of `2`. This means `n = 1 * (n - 2) + 2`.
- Therefore, the representation of `n` in base `n - 2` is always `12` (for `n > 4`).
- The string "12" is not a palindrome.
- For the edge case `n = 4`, the base to check is `b = 2`. `4` in base `2` is `100`, which is not a palindrome.
- Conclude that for any `n >= 4`, the number is never strictly palindromic.
- The function can simply return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean isStrictlyPalindromic(int n) { return false; }
}

```

### Python

```python
class Solution:
    def isStrictlyPalindromic(self, n: int) -> bool: return False

```

### CPP

```cpp
class Solution {
public:
  bool isStrictlyPalindromic(int n) { return false; }
};

```