2396. Strictly Palindromic Number Solution

The problem

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⁵

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.

Python

def is_palindrome(s):
    return s == s[::-1]


def to_base(n, base):
    digits = ''
    while n > 0:
        digits += str(n % base)
        n //= base
    return digits[::-1]


def is_strictly_palindromic(n):
    for base in range(2, n - 1):
        if not is_palindrome(to_base(n, base)):
            return False
    return True


n = 9
print(is_strictly_palindromic(n))

Java

public class Main {
    public static boolean isPalindrome(String str) {
        int len = str.length();
        for (int i = 0; i < len / 2; i++) {
            if (str.charAt(i) != str.charAt(len - i - 1)) return false;
        }
        return true;
    }

    public static String toBase(int n, int base) {
        StringBuilder result = new StringBuilder();
        while (n > 0) {
            result.append(n % base);
            n /= base;
        }
        return result.reverse().toString();
    }

    public static boolean isStrictlyPalindromic(int n) {
        for (int base = 2; base <= n - 2; base++) {
            if (!isPalindrome(toBase(n, base)))
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 9;
        System.out.println(isStrictlyPalindromic(n));
    }
}

C++

#include <iostream>
#include <string>

bool isPalindrome(const std::string& str) {
    for (int i = 0, j = str.size() - 1; i < j; ++i, --j) {
        if (str[i] != str[j]) return false;
    }
    return true;
}

std::string toBase(int n, int base) {
    std::string result;
    while (n > 0) {
        result += (n % base) + '0';
        n /= base;
    }
    std::reverse(result.begin(), result.end());
    return result;
}

bool isStrictlyPalindromic(int n) {
    for (int base = 2; base <= n - 2; ++base) {
        if (!isPalindrome(toBase(n, base)))
            return false;
    }
    return true;
}

int main() {
    int n = 9;
    std::cout << (isStrictlyPalindromic(n) ? "true" : "false") << std::endl;
    return 0;
}

JavaScript

function isPalindrome(str) {
    return str === str.split('').reverse().join('');
}

function toBase(n, base) {
    let result = '';
    while (n > 0) {
        result = (n % base) + result;
        n = Math.floor(n / base);
    }
    return result;
}

function isStrictlyPalindromic(n) {
    for (let base = 2; base <= n - 2; base++) {
        if (!isPalindrome(toBase(n, base))) {
            return false;
        }
    }
    return true;
}

let n = 9;
console.log(isStrictlyPalindromic(n));

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool is_palindrome(const char* str) {
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        if (str[i] != str[len - i - 1]) {
            return false;
        }
    }
    return true;
}

void convert_to_base(int n, int base, char* buffer) {
    int index = 0;
    while (n > 0) {
        buffer[index++] = (n % base) + '0';
        n /= base;
    }
    buffer[index] = '\0';

    // Reverse the string
    for (int i = 0; i < index / 2; i++) {
        char temp = buffer[i];
        buffer[i] = buffer[index - i - 1];
        buffer[index - i - 1] = temp;
    }
}

bool is_strictly_palindromic(int n) {
    char buffer[33];
    for (int base = 2; base <= n - 2; base++) {
        convert_to_base(n, base, buffer);
        if (!is_palindrome(buffer)) {
            return false;
        }
    }
    return true;
}

int main() {
    int n = 9;
    printf("%s\n", is_strictly_palindromic(n) ? "true" : "false");
    return 0;
}

using System;

class Program
{
    static bool IsPalindrome(string s)
    {
        int len = s.Length;
        for (int i = 0; i < len / 2; i++)
        {
            if (s[i] != s[len - i - 1])
                return false;
        }
        return true;
    }

    static string ToBase(int n, int base)
    {
        char[] digits = new char[32];
        int idx = 0;
        while (n > 0)
        {
            digits[idx++] = (char)(n % base + '0');
            n /= base;
        }
        Array.Reverse(digits, 0, idx);
        return new String(digits, 0, idx);
    }

    static bool IsStrictlyPalindromic(int n)
    {
        for (int base = 2; base <= n - 2; base++)
        {
            if (!IsPalindrome(ToBase(n, base)))
                return false;
        }
        return true;
    }

    static void Main(string[] args)
    {
        int n = 9;
        Console.WriteLine(IsStrictlyPalindromic(n));
    }
}

Using Python's powerful slicing capabilities, this solution twins palindrome detection and base conversion in compact, expressive functions. Each base conversion is checked for palindromicity and a binary result is outputted accordingly.

Complexity

Time Complexity: O(n * log(n)) considering the cost of base conversions and reversals for palindrome checks.
Space Complexity: O(log(n)) due to temporary string storage during base conversions.

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.

Python

def is_strictly_palindromic(n):
    return n < 4

n = 9
print(is_strictly_palindromic(n))

Java

public class Main {
    public static boolean isStrictlyPalindromic(int n) {
        return n < 4;
    }

    public static void main(String[] args) {
        int n = 9;
        System.out.println(isStrictlyPalindromic(n));
    }
}

C++

#include <iostream>

bool isStrictlyPalindromic(int n) {
    return n < 4;
}

int main() {
    int n = 9;
    std::cout << (isStrictlyPalindromic(n) ? "true" : "false") << std::endl;
    return 0;
}

JavaScript

function isStrictlyPalindromic(n) {
    return n < 4;
}

let n = 9;
console.log(isStrictlyPalindromic(n));

#include <stdio.h>
#include <stdbool.h>

bool is_strictly_palindromic(int n) {
    return (n < 4);
}

int main() {
    int n = 9;
    printf("%s\n", is_strictly_palindromic(n) ? "true" : "false");
    return 0;
}

using System;

class Program
{
    static bool IsStrictlyPalindromic(int n)
    {
        return n < 4;
    }

    static void Main()
    {
        int n = 9;
        Console.WriteLine(IsStrictlyPalindromic(n));
    }
}

Utilizing Python's straightforward syntactic style, this solution bypasses direct iteration or conversion work with a strategic base condition test that broadly and effectively eliminates usual doubt via implication.

Complexity

Time Complexity: O(1), accomplished through intuitive deduction.
Space Complexity: O(1), eschewing added data structures or dynamic allocation.

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

TypeScript

function isStrictlyPalindromic(n: number): boolean {
    return false;
}

func isStrictlyPalindromic(n int) bool {
	return false
}

Rust

impl Solution {
    pub fn is_strictly_palindromic(n: i32) -> bool {
        false
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Base Conversion and Palindrome Check	Time Complexity: O(n * log(n)) considering the cost of base conversions and reversals for palindrome checks. Space Complexity: O(log(n)) due to temporary string storage during base conversions.
Mathematical Insight on Palindromicity	Time Complexity: O(1), accomplished through intuitive deduction. Space Complexity: O(1), eschewing added data structures or dynamic allocation.
Quick Thinking	–

Complexity analysis

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"

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.

Strictly Palindromic Number solution and explanation

The problem

Approach overview

Approach 1: Iterative Base Conversion and Palindrome Check

Approach 2: Mathematical Insight on Palindromicity

Approach 3: Quick Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Strictly Palindromic Number solution and explanation

The problem

Approach overview

Approach 1: Iterative Base Conversion and Palindrome Check

Approach 2: Mathematical Insight on Palindromicity

Approach 3: Quick Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems