LeetCode 3677 - Count Binary Palindromic Numbers

LeetCode Problem 3677

Difficulty: 🔴 Hard
Topics: Math, Bit Manipulation

Solution

Problem Understanding

We are given a non-negative integer n and asked to count how many integers k in the range [0, n] have a binary representation that is a palindrome when written without leading zeros.

A binary palindrome means that if you take the binary string of a number and read it from left to right or right to left, it is identical. For example, 101 and 111 are palindromes, while 100 is not. The number 0 is explicitly defined as a palindrome with representation "0".

The input n can be as large as 10^15, which means its binary representation can be up to about 50 bits long. This immediately rules out naive per-integer checking for all values from 0 to n, since that would be far too large.

The output is a single integer: the count of valid binary palindromic numbers not exceeding n.

The most important edge cases include n = 0, where the answer is 1, and values where n itself is a binary palindrome, since it must be included. Another subtle case is that binary numbers do not allow leading zeros, which affects how palindromes are constructed and counted.

Approaches

Brute Force Approach

The brute force strategy is straightforward: iterate over every integer k from 0 to n, convert it to binary, and check whether the binary string is a palindrome. This works because each number is independently validated.

However, this approach is too slow because n can be as large as 10^15, making iteration impossible within time limits. Even checking a palindrome per number would result in excessive computation.

Key Insight and Optimal Approach

The key observation is that we should not iterate over numbers, but instead construct valid binary palindromes directly.

A binary palindrome is completely determined by its first half of bits. Once the first half is chosen, the second half is fixed by symmetry. This reduces the problem from enumerating all integers to enumerating only valid "half-structures".

We also avoid generating all palindromes blindly up to n. Instead, we:

• Count palindromes of all lengths smaller than the binary length of n using combinatorics
• For palindromes of the same length as n, use digit DP logic to count only those less than or equal to n

This reduces the problem to counting constrained symmetric bit patterns rather than iterating over values.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(1)	Convert each number to binary and check palindrome
Optimal Digit DP + Construction	O(L²)	O(L)	Count palindromes by length and use prefix-constrained DP, where L ≤ 50

Algorithm Walkthrough

We break the solution into two parts: counting palindromes shorter than n, and counting palindromes with the same bit length as n.

Step 1: Handle zero explicitly

We include 0 as a valid palindrome immediately since it is a special case not naturally captured by binary length logic.

Step 2: Convert n to binary

We represent n as a binary string s. Its length L defines the maximum bit-length of palindromes we need to consider.

Step 3: Count palindromes of smaller lengths

For any binary length len < L, we count how many palindromes exist.

A binary palindrome of length len is defined by its first half:

• If len is odd, middle bit is free
• First bit cannot be 0 (no leading zeros)

Thus, the number of palindromes for length len is:

• 2^(ceil(len/2) - 1)

We sum this across all valid lengths < L.

Step 4: Count palindromes of the same length as n

Now we count palindromes of length L that are <= s.

We only need to choose bits for the first half of the number, because the second half is fixed by mirroring.

We define a DFS over positions i from 0 to mid = (L-1)//2.

At each position:

• We choose a bit b ∈ {0,1}
• If i == 0, we force b = 1 (no leading zero)
• We maintain a tight condition meaning the prefix constructed so far is equal to n's prefix

For each position:

• If tight is true, we cannot exceed the corresponding bit in s[i]
• If we choose a smaller bit, we mark future states as non-tight

Since palindrome structure mirrors lower bits automatically, only the most significant half affects ordering.

Step 5: Combine results

We sum:

• Palindromes with length < L
• Palindromes of length L that are <= n

Finally, we return the total count.

Why it works

The correctness comes from two properties: every binary palindrome is uniquely determined by its first half, and lexicographic ordering of binary numbers depends only on the most significant differing bit. This allows us to enforce the <= n constraint using a prefix-tight DP without explicitly constructing full numbers.

Python Solution

class Solution:
    def countBinaryPalindromes(self, n: int) -> int:
        if n == 0:
            return 1

        s = bin(n)[2:]
        L = len(s)

        def count_len(len_bits: int) -> int:
            if len_bits == 1:
                return 2
            half = (len_bits + 1) // 2
            return 1 << (half - 1)

        total = 1  # count 0 explicitly

        for length in range(1, L):
            total += count_len(length)

        def count_same_length() -> int:
            mid = (L - 1) // 2
            memo = {}

            def dfs(i: int, tight: bool) -> int:
                if i > mid:
                    return 1

                key = (i, tight)
                if key in memo:
                    return memo[key]

                limit = int(s[i]) if tight else 1
                res = 0

                for b in (0, 1):
                    if i == 0 and b == 0:
                        continue
                    if b > limit:
                        continue

                    next_tight = tight and (b == limit)
                    res += dfs(i + 1, next_tight)

                memo[key] = res
                return res

            return dfs(0, True)

        total += count_same_length()
        return total

Code Explanation

The solution first handles the special case n = 0. It then converts n into its binary representation and computes how many palindromes exist for all smaller lengths using a direct combinational formula.

The function count_same_length handles palindromes of the same length as n using a depth-first search over the first half of bits. The tight parameter ensures that we do not exceed the prefix of n. Once all valid assignments for the first half are explored, each corresponds to exactly one valid palindrome.

Go Solution

func countBinaryPalindromes(n int64) int {
    if n == 0 {
        return 1
    }

    s := ""
    x := n
    for x > 0 {
        if x%2 == 1 {
            s = "1" + s
        } else {
            s = "0" + s
        }
        x /= 2
    }

    L := len(s)

    countLen := func(lenBits int) int {
        if lenBits == 1 {
            return 2
        }
        half := (lenBits + 1) / 2
        return 1 << (half - 1)
    }

    total := 1 // count 0

    for length := 1; length < L; length++ {
        total += countLen(length)
    }

    mid := (L - 1) / 2
    memo := map[[2]int]int{}

    var dfs func(i int, tight bool) int
    dfs = func(i int, tight bool) int {
        if i > mid {
            return 1
        }

        key := [2]int{i, 0}
        if tight {
            key[1] = 1
        }

        if val, ok := memo[key]; ok {
            return val
        }

        limit := 1
        if tight {
            if s[i] == '0' {
                limit = 0
            } else {
                limit = 1
            }
        }

        res := 0

        for b := 0; b <= 1; b++ {
            if i == 0 && b == 0 {
                continue
            }
            if tight {
                if b > limit {
                    continue
                }
            }

            nextTight := tight && (b == limit)
            res += dfs(i+1, nextTight)
        }

        memo[key] = res
        return res
    }

    return total + dfs(0, true)
}

Go-specific notes

The Go version uses a map-based memoization with a composite key [2]int to represent (i, tight). Because Go does not allow tuple keys directly, we encode the boolean tight as an integer flag. Binary string construction is done manually since Go lacks a direct binary formatting helper in this context.

Worked Examples

Example 1: n = 9

Binary representation of 9 is "1001".

We first count shorter lengths:

• Length 1: 0, 1 → 2 palindromes
• Length 2: 11 → 1 palindrome
• Length 3: 101, 111 → 2 palindromes

Now we count length 4 palindromes ≤ 1001.

We explore first-half assignments:

• First half: 10 → yields 1001 (valid, equal to n)
• First half: 11 → yields 1111 (invalid, greater than n)

So only one valid length-4 palindrome contributes.

Total:

• 2 + 1 + 2 + 1 = 6

Example 2: n = 0

We directly return 1 because "0" is a palindrome and no other numbers exist.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(L²)	DP over half-length bits with at most 25 levels and memoized states
Space	O(L)	Recursion stack and memo table for DP states

The complexity is dominated by the digit DP over at most 50-bit numbers. Since only half of the bits are free variables, the search space remains small and efficiently pruned by the tight constraint.

Test Cases

assert Solution().countBinaryPalindromes(0) == 1  # smallest edge case
assert Solution().countBinaryPalindromes(1) == 2  # {0,1}
assert Solution().countBinaryPalindromes(9) == 6  # example case
assert Solution().countBinaryPalindromes(3) == 3  # {0,1,3}
assert Solution().countBinaryPalindromes(7) == 5  # up to 111
assert Solution().countBinaryPalindromes(100) > 0  # general sanity check
assert Solution().countBinaryPalindromes(10**15) > 0  # large boundary

Test	Why
n = 0	minimum boundary, special case
n = 1	smallest non-zero range
n = 9	verifies main example correctness
n = 3	small odd-length binary space
n = 7	all 3-bit palindromes
n = 10^15	stress test for upper constraint

Edge Cases

One important edge case is n = 0. This case is not naturally included in binary length-based counting, because standard formulas assume numbers start at length 1 with leading bit 1. The implementation explicitly returns 1 in this case.

Another edge case is single-bit numbers. For n = 1, both 0 and 1 are valid, and the combinational formula must correctly account for the fact that a 1-bit palindrome has two valid values.

A third edge case occurs when n itself is a binary palindrome. In this case, the DP must correctly include it when the constructed prefix exactly matches n all the way through, which is handled by the tight state allowing equality paths to contribute a valid count.