Is Strictly Palindromic Number easy or hard?

The implementation looks medium difficulty because it involves base conversion and palindrome checks. However, once the mathematical property is recognized, the problem becomes trivial with an O(1) solution. The challenge is spotting the insight rather than writing complex code.

Strictly Palindromic Number Python/Java solution

In Python, Java, C++, or similar languages, the optimal implementation simply returns false for any valid input because n ≥ 4 guarantees a non-palindromic representation in base n−2. Many editorial solutions show both the brute-force base conversion approach and the constant-time mathematical proof.

How to solve Strictly Palindromic Number in O(1)?

Use the property of positional number systems: for n ≥ 4, writing n in base (n−2) produces the digits "12". Since "12" is not a palindrome, the number fails the strictly palindromic requirement immediately. The function can simply return false without performing any base conversions.

What is the best approach for Strictly Palindromic Number?

The optimal approach uses a mathematical observation: for any integer n ≥ 4, the representation of n in base (n−2) is always "12", which is not a palindrome. Because the problem requires the number to be palindromic in every base from 2 to n−2, this single counterexample proves the answer is always false. The final algorithm runs in O(1) time and O(1) space.

Is Strictly Palindromic Number asked at Google/Amazon/Meta?

Brainteaser-style math problems like this appear in technical interviews at large companies including Google and Meta, especially in early screening rounds. The goal is to see whether candidates recognize patterns and mathematical shortcuts instead of implementing brute-force simulations.

What data structure is used in Strictly Palindromic Number?

The brute-force solution temporarily stores digits of the converted number in a string or array and checks palindromes using two pointers. The optimal mathematical solution does not require any data structure because the answer is derived from number representation properties.

What is the time complexity of Strictly Palindromic Number?

The brute-force interpretation requires converting n into every base from 2 to n−2 and checking if the digits form a palindrome, which takes O(n log n) time and O(log n) space. With the mathematical insight that base n−2 always produces "12", the optimal solution runs in constant O(1) time and space.

Description Hints 2 Solution Video 7:33

2396. Strictly Palindromic Number

Medium90.3% acceptance2 companies

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 <= 10⁵

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Consider the representation of the given number in the base n - 2.

Hint 2

The number n in base (n - 2) is always 12, which is not palindromic.

7:33

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution