Leetcode problem 97 - Strictly Palindromic Number

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

/**
 * @param {number} n
 * @return {boolean}
 */
var isStrictlyPalindromic = function (n) {
  // Iterate through bases from 2 to n - 2 (inclusive)
  for (let i = 2; i <= n - 2; i++) {
    // Convert the number to a string representation in the current base
    const str = n.toString(i);

    // Initialize pointers for checking palindromicity
    let left = 0;
    let right = str.length - 1;

    // Check if the string representation is palindromic
    while (left < right) {
      // If the characters at the left and right pointers are not equal, it's not palindromic
      if (str[left] !== str[right]) {
        return false; // Return false if not palindromic
      }
      left++;
      right--;
    }
  }

  // If the string representation is palindromic for all bases, return true
  return true;
};

Time comeplexity is O(n logn) where n is the input number. The algorithm iterates through all bases from 2 to n - 2 (inclusive), and for each base, it converts the number to a string representation in that base. The time complexity of converting a number to a string representation in a given base is O(logn) where n is the number. Therefore, the overall time complexity is O(n logn).

Space complexity is O(logn) since the space used by the string representation of the number in a given base is O(logn).