Skip to main content
Talentd

Strictly Palindromic Number - Solution & Explanation

MediumMathTwo PointersBrainteaser14 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 <= 105

Approach Overview

Problem 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 1: Iterative Base Conversion and Palindrome Check

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Mathematical Insight on Palindromicity

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Quick Thinking

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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(log(n)) for storing number strings temporarily.

Mathematical Insight on Palindromicity

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.

Quick Thinking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Base Conversion and Palindrome CheckO(n log n)O(log n)When implementing the definition directly or demonstrating base conversion and palindrome checking logic
Mathematical Insight on PalindromicityO(1)O(1)Optimal interview solution once you recognize that base n-2 always produces the non-palindrome "12"

Video Solution

2396. Strictly Palindromic Number | LeetCode Biweekly Contest 86 | LeetCode 2396 • Bro Coders • 3,649 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Strictly Palindromic Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Palindrome Number

Next

Stone Game