Skip to content

2595. Number of Even and Odd Bits

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:

  • 1 <= n <= 1000

Solutions

Solution 1: Enumerate

Thinking

\(n\) is at most \(10^3\), so walking bits from low to high is enough. Flip the index with \(i\oplus 1\) and increment the matching counter when the bit is set.

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 = 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: Bit Manipulation

Thinking

Solution 1 is linear in the bit length. Even indices are exactly the mask \(0\texttt{x}5555\); \(\textit{bit\_count}(n\&\textit{mask})\) is the even tally, and the complement mask yields the odd tally in constant time.

We can define a mask \(\textit{mask} = \text{0x5555}\), which is represented in binary as \(\text{0101 0101 0101 0101}_2\). Then, performing a bitwise AND operation between \(n\) and \(\textit{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 \(\textit{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.

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]
    }
}

Comments