Strictly Palindromic Number

Strictly Palindromic Number

What is this problem about?

A Strictly Palindromic Number is defined as a number n that is a palindrome in every base from 2 up to n-2. The task is to write a function that takes an integer n and returns true if it meets this strict criteria, and false otherwise. While it sounds like a complex math and base-conversion problem, it contains a clever mathematical "trap" that simplifies the logic significantly for larger numbers.

Why is this asked in interviews?

This Strictly Palindromic Number interview question is often used by Amazon and Google as a "brainteaser." It tests whether a candidate will blindly jump into coding a complex solution or if they will pause to analyze the mathematical properties of the problem. It evaluates critical thinking and the ability to find "short-circuit" conditions. Interviewers want to see if you can prove whether such a number even exists for n > 4.

Algorithmic pattern used

The problem falls under the Brainteaser, Math, Two Pointers interview pattern. The mathematical insight is as follows: for any n > 4, consider the base n - 2. In base n - 2, the number n is represented as 12 (since 1 * (n-2) + 2 = n). The digits are 1 and 2, which is clearly not a palindrome. Since the condition must hold for all bases from 2 to n-2, and it fails for base n-2 for all n > 4, the answer is always false for any n the problem is likely to provide (usually n >= 4).

Example explanation

Let's check n = 4. Bases to check: 2 to 4-2=2. Just base 2.

• 4 in base 2 is 100. Not a palindrome. Result: false. Let's check n = 5. Bases: 2 to 3.
• 5 in base 2 is 101 (Palindrome).
• 5 in base 3 is 12 (Not a palindrome). Result: false. Let's check n = 6. Bases: 2 to 4.
• 6 in base 4 is 12 (Not a palindrome). Result: false. As we see, as soon as we hit base n-2, the representation 12 breaks the palindromic property.

Common mistakes candidates make

The most common mistake is writing a full loop to convert the number to every base and checking for palindromes. While this "works," it misses the point of the brainteaser and shows a lack of mathematical intuition. Another mistake is not correctly handling the base conversion logic or the two-pointer palindrome check. Some candidates might also misread the range of bases, starting from 1 or ending at n, which changes the result.

Interview preparation tip

In interviews, always look for the constraints and the mathematical boundaries. If a problem asks you to check a condition for "all" values in a range, see if you can find a single value that always fails. This "proof by contradiction" or "counter-example" approach is a great way to save time. For base conversion, remember the standard algorithm: repeatedly take n % base to get the digits and n // base to continue.