Count Binary Palindromic Numbers - Solution & Explanation

Problem Overview: Given an integer limit, count how many numbers have a binary representation that reads the same forward and backward. These are binary palindromes such as 1, 3 (11), 5 (101), or 9 (1001). The challenge is counting them efficiently without scanning every number.

Approach 1: Brute Force Binary Check (O(n log n) time, O(1) space)

The straightforward solution iterates from 1 to n. Convert each number to binary and check if the bit string is a palindrome using two pointers from both ends. The palindrome check takes O(log n) time because the binary length of a number is log₂ n. This approach is easy to implement but inefficient for large limits since every number must be inspected.

This method still appears in interviews as a starting point. It shows you recognize the definition of a binary palindrome and can implement a direct verification using bit manipulation or string comparison.

Approach 2: Construct Palindromes by Length (O(log n) time, O(1) space)

Instead of checking every number, generate binary palindromes directly. A binary palindrome is defined by its first half; the second half mirrors it. For a palindrome of length L, choose the first ceil(L/2) bits and mirror them to form the rest. Iterate through possible bit lengths up to log₂ n, count how many valid prefixes exist, and construct candidates using bit operations.

For each prefix, build the mirrored number using shifts and bit masking. Stop when the constructed value exceeds n. Because the number of binary lengths is only about log₂ n, and each prefix directly produces a palindrome, the algorithm avoids scanning the entire numeric range. This turns a linear search into a logarithmic one using simple operations like shifting and reversing bits.

The key observation is symmetry: once the left half is fixed, the right half is determined. Counting possible prefixes becomes a small math problem combined with efficient bit manipulation. This is the technique typically used in optimized competitive programming solutions.

Recommended for interviews: Start with the brute force explanation because it directly models the problem definition. Then move to the palindrome construction idea. Interviewers expect the optimized approach since it demonstrates understanding of binary structure, bit operations, and how to reduce a search space using symmetry.