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 ifn _isstrictly palindromic and _false otherwise.

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

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4

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 <= 10^5

Solution

Method 1 - Mathematical Observation (Brainteaser)

Intuition

For any n ≥ 4, there is always at least one base b (2 ≤ b ≤ n-2) such that the representation of n in base b is not a palindrome. In fact, for n ≥ 4, n in base n-2 is always ‘2 0’, which is not a palindrome. Thus, no number n ≥ 4 is strictly palindromic.

Approach

Return false for all n ≥ 4.

Code

1
2
3
4
5
6

class Solution {
public:
    bool isStrictlyPalindromic(int n) {
        return false;
    }
};
1
2
3

func isStrictlyPalindromic(n int) bool {
    return false
}
1
2
3
4
5

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

fun isStrictlyPalindromic(n: Int): Boolean = false
1
2

def isStrictlyPalindromic(n: int) -> bool:
    return False
1
2
3

pub fn is_strictly_palindromic(_n: i32) -> bool {
    false
}
1
2
3

function isStrictlyPalindromic(n: number): boolean {
    return false;
}

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)