Strictly Palindromic Number - Practice Coding Problems

Strictly Palindromic Number - 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.

Input & Output

Example 1 — Small Number

$ Input: n = 9

› Output: false

💡 Note: In base 2: 9 = 1001 (palindromic), but in base 3: 9 = 100 (not palindromic), so return false

Example 2 — Very Small Number

$ Input: n = 4

› Output: false

💡 Note: Need to check bases [2]. In base 2: 4 = 100 (not palindromic), so return false

Example 3 — Edge Case

$ Input: n = 2

› Output: false

💡 Note: No bases to check (range [2, 0] is empty), but by definition return false

Constraints

1 ≤ n ≤ 2 × 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n = 9

Process

Must check palindrome property in bases 2 through 7

Output

Return false - impossible to satisfy all bases

Key Takeaway

🎯 Key Insight: The constraint is mathematically impossible to satisfy for any meaningful input

Asked in

G Google 15 f Meta 8 a Amazon 12

This is essentially a trick question with a mathematical twist. The key insight is that no integer can be strictly palindromic due to the constraint requirements. The optimal approach simply returns false in O(1) time and O(1) space, making it one of the most efficient problems possible.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Insight - Direct False	O(1)	O(1)	Use mathematical proof that no number > 4 can be strictly palindromic
Brute Force - Check All Bases	O(n² log n)	O(log n)	Convert n to each base from 2 to n-2 and check if each representation is palindromic

Mathematical Insight - Direct False — Algorithm Steps

Step 1: Check if n ≤ 4 (only possible candidates)
Step 2: For n > 4, return false immediately based on mathematical proof
Step 3: For n ≤ 4, verify manually or return known results

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Constraint

Must be palindromic in ALL bases from 2 to n-2

Mathematical Proof

For n>4, range [2,n-2] too large - contradiction always exists

Direct Answer

Return false immediately without computation

Code -

solution.c — C

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

bool solution(int n) {
    // Mathematical proof shows no number > 4 can be strictly palindromic
    // For n > 4, there will always be at least one base in the range [2, n-2]
    // where n's representation is not palindromic
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Single constant-time check regardless of input size

✓ Linear Growth

Space Complexity

O(1)

No extra space needed, just return value

✓ Linear Space

15.0K Views

Low Frequency

~5 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Insight - Direct False — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler