Description
You are given a positive integer n.
Let even denote the number of even indices in the binary representation of n with value 1.
Let odd denote the number of odd indices in the binary representation of n with value 1.
Note that bits are indexed from right to left in the binary representation of a number.
Return the array [even, odd].
Example 1:
Input: n = 50
Output: [1,2]
Explanation:
The binary representation of 50 is 110010.
It contains 1 on indices 1, 4, and 5.
Example 2:
Input: n = 2
Output: [0,1]
Explanation:
The binary representation of 2 is 10.
It contains 1 only on index 1.
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.
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
function evenOddBit(n: number): number[] {
const ans = Array(2).fill(0);
for (let i = 0; n > 0; n >>= 1, i ^= 1) {
ans[i] += n & 1;
}
return ans;
}(code-box)
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
}
}(code-box)
Solution 2: Bit Manipulation
We can define a mask mask = 0x5555, which is represented in binary as 0101 0101 0101 0101_2. Then, performing a bitwise AND operation between n and mask will give us the bits at even indices in the binary representation of n. Performing a bitwise AND operation between n and the complement of mask will give us the bits at odd indices in the binary representation of n. We can count the number of 1s in these two results.
The time complexity is O(1), and the space complexity is O(1). Here, n is the given integer.
PythonJavaC++GoTypeScriptRust
class Solution:
def evenOddBit(self, n: int) -> List[int]:
mask = 0x5555
even = (n & mask).bit_count()
odd = (n & ~mask).bit_count()
return [even, odd](code-box)
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};
}
}(code-box)
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};
}
};(code-box)
func evenOddBit(n int) []int {
mask := 0x5555
even := bits.OnesCount32(uint32(n & mask))
odd := bits.OnesCount32(uint32(n & ^mask))
return []int{even, odd}
}(code-box)
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;
}(code-box)
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]
}
}(code-box)
