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.
This approach involves converting the number to all bases between 2 and n-2 and checking if the representation is palindromic. This involves two main tasks: base conversion and palindrome checking. In base conversion, repeatedly divide n by the base and collect remainders. These remainders, when reversed, form the number in the target base. For a palindrome, check if the string representation is the same forwards and backwards.
This solution iteratively converts the number to each base from 2 to n-2, storing results in a buffer. It checks if the string representation of each number is a palindrome by comparing symmetric positions within the string. If any representation is not palindromic, the function returns false.
Time Complexity: O(n * log(n)) due to converting numbers to different bases and checking each one for being palindromic.
Space Complexity: O(log(n)) for storing number strings temporarily.
This approach leverages a mathematical insight about the nature of base representations. The key observation is recognizing innate characteristics of numbers in lower ranges being palindromic, independent of certain high-value bases, hence revealing patterns directly without base conversion. Specifically, this approach utilizes observations in combinatorics and number theory that no number beyond n > 4 can be strictly palindromic.
This C solution hinges on the realization that no number n > 4 can be strictly palindromic as defined, thus this solution instantly returns false without any arithmetic computation. It reflects a pattern observed mathematically rather than computed iteratively, thus omitting unnecessary steps.
Time Complexity: O(1) since the solution is resolved by a single conditional evaluation.
Space Complexity: O(1) with no additional storage needed except numerical input.
When n = 4, its binary representation is 100, which is not a palindrome;
When n \gt 4, its (n - 2)-ary representation is 12, which is not a palindrome.
Therefore, we can directly return false.
The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Base Conversion and Palindrome Check | Time Complexity: O(n * log(n)) due to converting numbers to different bases and checking each one for being palindromic. |
| Mathematical Insight on Palindromicity | Time Complexity: O(1) since the solution is resolved by a single conditional evaluation. |
| Quick Thinking | — |
| 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" |
2396. Strictly Palindromic Number | LeetCode Biweekly Contest 86 | LeetCode 2396 • Bro Coders • 3,529 views views
Watch 9 more video solutions →Practice Strictly Palindromic Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor