3677. Count Binary Palindromic Numbers
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".
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
int helper(string& b, string& s, int l, int r) {
if(b < s) return 0;
if(l == r) {
s[l] = '1';
if(helper(b,s,l+1,r-1)) return 2;
s[l] = '0';
return helper(b,s,l+1,r-1);
}
if(l > r) return 1;
if(b[l] == '0') return helper(b,s,l+1,r-1);
s[l] = s[r] = '1';
return pow(2, (r - l) / 2) + helper(b,s,l+1,r-1);
}
public:
int countBinaryPalindromes(long long n) {
if(n <= 1) return 1 + n;
string binary = "";
while(n) {
binary.push_back((n % 2) +'0');
n /= 2;
}
reverse(begin(binary), end(binary));
int res = 2;
for(int len = 2; len < binary.size(); len++) {
res += pow(2,(len - 1) / 2 );
}
string now = string(binary.size(), '0');
now.front() = now.back() = '1';
res += helper(binary, now, 1, binary.size() - 2);
return res;
}
};
|
