Watch 10 video solutions for Strictly Palindromic Number, a medium level problem involving Math, Two Pointers, Brainteaser. This walkthrough by Bro Coders has 3,529 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105Problem Overview: A number n is strictly palindromic if its representation is a palindrome in every base from 2 to n-2. The task is to check whether such a number exists for the given input. At first glance this looks like repeated base conversion and palindrome validation, but a mathematical observation completely eliminates the need for computation.
Approach 1: Iterative Base Conversion and Palindrome Check (O(n log n) time, O(log n) space)
The direct approach follows the definition. Iterate through every base b from 2 to n-2. Convert n into base b by repeatedly dividing by b and collecting remainders. Store the digits in an array or string, then check whether the sequence is a palindrome using a two pointers comparison from both ends.
If any base representation fails the palindrome check, return false. If all bases pass, return true. Each base conversion takes O(log_b n) digits, which is O(log n) in the worst case. Since you test roughly n bases, the total time becomes O(n log n). Space usage is O(log n) to store digits during conversion. This approach mirrors the problem definition and demonstrates understanding of base conversion and palindrome checking.
Approach 2: Mathematical Insight on Palindromicity (O(1) time, O(1) space)
The key observation comes from number representation theory. For any integer n ≥ 4, consider base b = n - 2. In that base, the number n is written as 12. The digits differ, so the representation is not a palindrome.
This immediately proves that no integer n ≥ 4 can be strictly palindromic. Since the problem constraints guarantee n ≥ 4, the answer is always false. The entire computation reduces to returning a constant value without performing base conversions.
This reasoning relies on simple properties of positional number systems and falls under math and brainteaser style interview questions. Interviewers often include such problems to test whether you search for mathematical structure instead of brute forcing the definition.
Recommended for interviews: Start by explaining the brute force approach because it directly follows the definition and shows you can implement base conversion and palindrome validation. Then present the mathematical observation that base n-2 always produces 12, proving the answer is always false. Demonstrating the insight after outlining brute force signals strong problem‑solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Base Conversion and Palindrome Check | O(n log n) | O(log n) | When implementing the definition directly or demonstrating base conversion and palindrome checking logic |
| Mathematical Insight on Palindromicity | O(1) | O(1) | Optimal interview solution once you recognize that base n-2 always produces the non-palindrome "12" |