Scale Engineer

Strictly Palindromic Number

Med
#2180Time: 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)`.
Patterns
MathTwo Pointers

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem