3677. Count Binary Palindromic Numbers
SourceWeekly Contest 466 Q4DifficultyHardRating2222
Description
You are given a non-negative integer n.
A non-negative integer is called binary-palindromic if its binary representation (written without leading zeros) reads the same forward and backward.
Return the number of integers k such that 0 <= k <= n and the binary representation of k is a palindrome.
Note: The number 0 is considered binary-palindromic, and its representation is "0".
Example 1:
Input: n = 9
Output: 6
Explanation:
The integers k in the range [0, 9] whose binary representations are palindromes are:
0 → "0"1 → "1"3 → "11"5 → "101"7 → "111"9 → "1001"
All other values in [0, 9] have non-palindromic binary forms. Therefore, the count is 6.
Example 2:
Input: n = 0
Output: 1
Explanation:
Since "0" is a palindrome, the count is 1.
Constraints:
0 <= n <= 1015
Solutions
Solution 1
Thinking
Count binary palindromes in \([0,n]\). \(n\) is large, so a palindrome is generated from its first half.
Let \(n\) have bit length \(L\). Palindromes shorter than \(L\) are counted by length; those of length \(L\) come from first halves whose mirror is at most \(n\).
Odd lengths have a free center bit. Treat the first half as an integer, mirror it, compare with \(n\), and add every shorter length.
1 | |
1 | |
1 | |
1 | |