Strictly Palindromic Number

medium two pointers palindrome number base math

Problem

An integer n is strictly palindromic if, for every base b from 2 to n - 2 (inclusive), the representation of n in base b reads the same forward and backward. Given an integer n, return true if it is strictly palindromic and false otherwise.

Inputn = 9

Outputfalse

Base 2: 9 = 1001 (palindrome). Base 3: 9 = 100 (not a palindrome), so we return false.

Inputn = 4

Outputfalse

Only base 2 is checked: 4 = 100, which is not a palindrome.

n (integer, 4 to 30)

def is_strictly_palindromic(n):
    for b in range(2, n - 1):
        digits = []
        m = n
        while m > 0:
            digits.append(m % b)
            m //= b
        i, j = 0, len(digits) - 1
        while i < j:
            if digits[i] != digits[j]:
                return False
            i += 1
            j -= 1
    return True

function isStrictlyPalindromic(n) {
  for (let b = 2; b <= n - 2; b++) {
    const digits = [];
    let m = n;
    while (m > 0) {
      digits.push(m % b);
      m = Math.floor(m / b);
    }
    let i = 0, j = digits.length - 1;
    while (i < j) {
      if (digits[i] !== digits[j]) return false;
      i++;
      j--;
    }
  }
  return true;
}

boolean isStrictlyPalindromic(int n) {
    for (int b = 2; b <= n - 2; b++) {
        List<Integer> digits = new ArrayList<>();
        int m = n;
        while (m > 0) {
            digits.add(m % b);
            m /= b;
        }
        int i = 0, j = digits.size() - 1;
        while (i < j) {
            if (!digits.get(i).equals(digits.get(j))) return false;
            i++;
            j--;
        }
    }
    return true;
}

bool isStrictlyPalindromic(int n) {
    for (int b = 2; b <= n - 2; b++) {
        vector<int> digits;
        int m = n;
        while (m > 0) {
            digits.push_back(m % b);
            m /= b;
        }
        int i = 0, j = (int)digits.size() - 1;
        while (i < j) {
            if (digits[i] != digits[j]) return false;
            i++;
            j--;
        }
    }
    return true;
}

Explanation

The brute-force reading of the definition is: for every base b from 2 up to n - 2, write n in that base and test whether the digit string is a palindrome. As soon as one base fails, the answer is false; only if all bases pass do we return true.

Converting to base b is the usual repeated-division trick: take m % b as the next digit, then divide m by b, until m reaches 0. This yields the digits from least significant to most significant, which is fine because palindrome-checking is symmetric.

To test the palindrome we use two pointers: i starts at the front of the digit list and j at the back. We compare digits[i] with digits[j]; if they ever differ the representation is not a palindrome. Otherwise we move i forward and j backward until they meet in the middle.

There is a beautiful shortcut: for any n ≥ 4, look at base b = n - 2. Since n = 1·(n-2) + 2, the representation is the two digits [2, 1] — read as 1 2 from most significant — which is never a palindrome. So the loop is guaranteed to hit a failing base, and the answer is always false.

The visualizer walks the bases in order, builds each base representation, then runs the two-pointer palindrome check digit by digit, stopping the moment a mismatch proves the number is not strictly palindromic.

Time: O(n log n) Space: O(log n)