Strictly Palindromic Number

Strictly Palindromic Number requires checking if n is palindromic in every base from 2 to n - 2. Using two-pointer scanning, you verify each representation quickly and track invariants to avoid unnecessary conversions. This approach efficiently identifies failures early and returns false as soon as a non-palindromic base is found.

Problem Statement

A number n is strictly palindromic if for every base b between 2 and n - 2, the representation of n in base b reads the same forwards and backwards. Your task is to check this property efficiently.

Given an integer n, return true if it is strictly palindromic and false otherwise. A string representation is palindromic if the first and last characters match and this property holds recursively inward, making two-pointer scanning a natural pattern to use.

Examples

Example 1

Input: n = 9

Output: false

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

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

Constraints

• 4 <= n <= 105

Solution Approach

Convert Number to Base

For each base b from 2 to n - 2, convert n to a string in that base. This allows you to inspect the digits directly and prepare for palindrome verification using two pointers.

Two-Pointer Palindrome Check

Use a left and right pointer to scan the base-b string representation of n. Move the pointers inward and compare digits. If any mismatch occurs, immediately return false, as n is not strictly palindromic.

Early Exit and Invariant Tracking

Track invariants like the length and first/last digit matches to optimize scanning. Stop checking further bases once a non-palindromic representation is found, reducing unnecessary computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to converting n into multiple bases and scanning each string. Space complexity is O(log n) for storing each base representation during the two-pointer check.

What Interviewers Usually Probe

• Asks how you would verify palindromic property in multiple bases efficiently.
• Hints at using two-pointer scanning instead of reversing strings for optimization.
• Questions about early exit conditions and invariant tracking to avoid extra work.

Common Pitfalls or Variants

Common pitfalls

• Assuming n can be strictly palindromic for n >= 4, which is always false in practice.
• Not stopping early when a base fails, leading to unnecessary computation.
• Using full string reversal for palindrome check instead of two-pointer comparison.

Follow-up variants

• Check if a number is palindromic only in prime bases between 2 and n - 2.
• Return all bases where n is not palindromic rather than just a boolean.
• Verify strictly palindromic property for a list of numbers efficiently using batch processing.

FAQ

What is a strictly palindromic number?

A strictly palindromic number reads the same forwards and backwards in every base from 2 to n - 2.

Why use two-pointer scanning for this problem?

Two-pointer scanning allows checking palindrome property in linear time without reversing strings, matching the problem pattern efficiently.

Can any number greater than 4 be strictly palindromic?

No, any integer n >= 4 is never strictly palindromic because in base n - 2, the representation is always 12, which is not a palindrome.

How do I optimize checking all bases?

Track invariants and stop as soon as a base produces a non-palindromic representation to reduce computation.

What should I focus on during interview for this problem?

Emphasize the two-pointer scanning with invariant tracking and clearly explain early exit reasoning for strictly palindromic checks.