题目描述
给你一个 正 整数 n
。
用 even
表示在 n
的二进制形式(下标从 0 开始)中值为 1
的偶数下标的个数。
用 odd
表示在 n
的二进制形式(下标从 0 开始)中值为 1
的奇数下标的个数。
返回整数数组 answer
,其中 answer = [even, odd]
。
样例
输入:n = 17
输出:[2,0]
解释:17 的二进制形式是 10001。
下标 0 和 下标 4 对应的值为 1。
共有 2 个偶数下标,0 个奇数下标。
输入:n = 2
输出:[0,1]
解释:2 的二进制形式是 10。
下标 1 对应的值为 1。
共有 0 个偶数下标,1 个奇数下标。
限制
1 <= n <= 1000
算法
(模拟) $O(\log n)$
- 根据题意逐一判断 $n$ 的二进制位。
时间复杂度
- 遍历 $O(\log n)$ 次二进制位,故时间复杂度为 $O(\log n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
vector<int> evenOddBit(int n) {
vector<int> ans(2, 0);
int b = 0;
while (n) {
if (n & 1)
++ans[b];
b ^= 1;
n >>= 1;
}
return ans;
}
};