Description#
You are given a positive integer n.
Let even denote the number of even indices in the binary representation of n (0-indexed) with value 1.
Let odd denote the number of odd indices in the binary representation of n (0-indexed) with value 1.
Return an integer array answer where answer = [even, odd].
Example 1:
Input: n = 17
Output: [2,0]
Explanation: The binary representation of 17 is 10001.
It contains 1 on the 0th and 4th indices.
There are 2 even and 0 odd indices.
Example 2:
Input: n = 2
Output: [0,1]
Explanation: The binary representation of 2 is 10.
It contains 1 on the 1st index.
There are 0 even and 1 odd indices.
Constraints:
Solutions#
Solution 1: Enumerate#
According to the problem description, enumerate the binary representation of $n$ from the low bit to the high bit. If the bit is $1$, add $1$ to the corresponding counter according to whether the index of the bit is odd or even.
The time complexity is $O(\log n)$ and the space complexity is $O(1)$. Where $n$ is the given integer.
1
2
3
4
5
6
7
8
9
| class Solution:
def evenOddBit(self, n: int) -> List[int]:
ans = [0, 0]
i = 0
while n:
ans[i] += n & 1
i ^= 1
n >>= 1
return ans
|
1
2
3
4
5
6
7
8
9
| class Solution {
public int[] evenOddBit(int n) {
int[] ans = new int[2];
for (int i = 0; n > 0; n >>= 1, i ^= 1) {
ans[i] += n & 1;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
vector<int> evenOddBit(int n) {
vector<int> ans(2);
for (int i = 0; n > 0; n >>= 1, i ^= 1) {
ans[i] += n & 1;
}
return ans;
}
};
|
1
2
3
4
5
6
7
| func evenOddBit(n int) []int {
ans := make([]int, 2)
for i := 0; n != 0; n, i = n>>1, i^1 {
ans[i] += n & 1
}
return ans
}
|
1
2
3
4
5
6
7
| function evenOddBit(n: number): number[] {
const ans = new Array(2).fill(0);
for (let i = 0; n > 0; n >>= 1, i ^= 1) {
ans[i] += n & 1;
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| impl Solution {
pub fn even_odd_bit(mut n: i32) -> Vec<i32> {
let mut ans = vec![0; 2];
let mut i = 0;
while n != 0 {
ans[i] += n & 1;
n >>= 1;
i ^= 1;
}
ans
}
}
|
Solution 2#
1
2
3
4
5
6
| class Solution:
def evenOddBit(self, n: int) -> List[int]:
mask = 0x5555
even = (n & mask).bit_count()
odd = (n & ~mask).bit_count()
return [even, odd]
|
1
2
3
4
5
6
7
8
| class Solution {
public int[] evenOddBit(int n) {
int mask = 0x5555;
int even = Integer.bitCount(n & mask);
int odd = Integer.bitCount(n & ~mask);
return new int[] {even, odd};
}
}
|
1
2
3
4
5
6
7
8
9
| class Solution {
public:
vector<int> evenOddBit(int n) {
int mask = 0x5555;
int even = __builtin_popcount(n & mask);
int odd = __builtin_popcount(n & ~mask);
return {even, odd};
}
};
|
1
2
3
4
5
6
| func evenOddBit(n int) []int {
mask := 0x5555
even := bits.OnesCount32(uint32(n & mask))
odd := bits.OnesCount32(uint32(n & ^mask))
return []int{even, odd}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function evenOddBit(n: number): number[] {
const mask = 0x5555;
const even = bitCount(n & mask);
const odd = bitCount(n & ~mask);
return [even, odd];
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
|
1
2
3
4
5
6
7
8
| impl Solution {
pub fn even_odd_bit(n: i32) -> Vec<i32> {
let mask: i32 = 0x5555;
let even = (n & mask).count_ones() as i32;
let odd = (n & !mask).count_ones() as i32;
vec![even, odd]
}
}
|
