002.md

2396. Strictly Palindromic Number

Difficulty: 🟡 Medium

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.

Examples:

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

Solutions

O(1) solution

There is no such a number in 4 <= n <= 10^5 which will be strictly palindromic for every base 2 and n-2. Because in n-2 base any number will be 12 which is not palindrome.

Python3

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

TypeScript

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

O(N log N) solution

Python3

class Solution:
    def isStrictlyPalindromic(self, n: int) -> bool:
        # for every integer between 2 and n-2
        # range end is not inclusive thus n-2+1 = n-1
        for i in range(2, n-1):
            # convert to base 2 and check palindrome or not
            base_2 = f"{i:b}"
            if base_2 != base_2[::-1]:
                return False
        return True

JavaScript

var isStrictlyPalindromic = function(n) {
    base = 2

    while(base<=n-2){
        x=n.toString(base)
        if(x==x.split('').reverse().join('')){
            isStrictPalindrome = true
            base++
        } else {
            return false
        }
    }

    return isStrictPalindrome
};

The given solution solves the problem by iterating through each base b between 2 and n-2 (inclusive). For each base, it converts n to its string representation in that base using the f"{n:b}" format. If the string representation is not a palindrome (i.e., it is not the same when read forward and backward), the solution immediately returns False. If all the string representations in different bases are palindromic, the solution returns True.

The algorithm follows these steps:

1. Iterate through each base b from 2 to n-2 (inclusive) using the range function.
2. Convert n to its string representation in base b using the f"{n:b}" format and assign it to the variable base_b.
3. Check if base_b is not equal to its reverse (base_b[::-1]). If they are not equal, return False immediately.
4. Repeat steps 2-3 for each base b in the range.
5. Return True if all the string representations in different bases are palindromic.

Complexity Analysis

The time complexity of the algorithm is O(N log N), where N is the value of n. This is because the algorithm iterates through each base b from 2 to n-2 and converts n to its string representation in that base, which takes O(log N) time.

The space complexity of the algorithm is O(log N) because it uses additional space to store the string representation of n in each base, and the number of digits in the string representation is O(log N).

Summary

The given solution determines whether the given integer n is strictly palindromic or not. It iterates through each base b from 2 to n-2 and converts n to its string representation in that base. If any of the string representations are not palindromic, the algorithm immediately returns False. If all the string representations are palindromic, the algorithm returns True. The algorithm has a time complexity of O(N log N) and a space complexity of O(log N), where N is the value of n. ** If you want to get community points please suggest solutions in other languages as merge requests. **