#2595

Easy

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Number of Even and Odd Bits

Count the number of 1s at even and odd indices in the binary representation of a given integer n.

Problem Statement

You are given a positive integer n. Your task is to count how many bits are set to 1 at even indices and odd indices in the binary representation of n. Indices are zero-based, with the least significant bit at index 0.

To solve the problem, you need to determine the count of 1s in even and odd positions. For example, in the binary representation of 50 (110010), there is one 1 at an even index and two 1s at odd indices.

Examples

Example 1

Input: n = 50

Output: [1,2]

The binary representation of 50 is 110010 . It contains 1 on indices 1, 4, and 5.

Example 2

Input: n = 2

Output: [0,1]

The binary representation of 2 is 10 . It contains 1 only on index 1.

Constraints

1 <= n <= 1000

Solution Approach

Bit Manipulation

To efficiently solve this problem, use bitwise operations to examine each bit of the binary representation of n. This allows you to check even and odd indices without converting the number to a string or array.

Two Integer Counters

Maintain two integer variables, one for counting even indices and one for counting odd indices. Iterate over the bits of n, checking if the current bit is 1 and increment the respective counter depending on whether the index is even or odd.

Shift and Masking

Use bit shifts to iterate through the binary representation of n, starting from the least significant bit. Mask the current bit using a bitwise AND operation and shift the number right to move through each bit.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of bits in n, which is logarithmic with respect to n. The space complexity is constant, as we only use two integer variables to store the counts.

What Interviewers Usually Probe

Look for an understanding of bit manipulation techniques.
Expect the candidate to optimize the solution with efficient operations like bit shifting.
Pay attention to the candidate’s ability to maintain multiple counters for specific conditions.

Common Pitfalls or Variants

Common pitfalls

Candidates may attempt a less efficient solution using string conversion or array manipulation.
Confusing even and odd indices, leading to incorrect counting.
Overcomplicating the solution with unnecessary loops or data structures.

Follow-up variants

Count bits at even and odd indices for larger integers.
Consider extending the problem to work with negative integers, adjusting for the sign bit.
Handle cases where the binary representation has fewer bits than the typical word length.

FAQ

What is the best way to count even and odd bits in the binary representation of a number?

The best way is to use bitwise operations with two counters—one for even indices and one for odd indices—while iterating through the bits of the number.

How can I avoid mistakes when counting bits at even and odd positions?

Be sure to clearly separate the handling of even and odd indices, and double-check your bitwise operations, especially with shifts and masks.

Can I solve the "Number of Even and Odd Bits" problem without bit manipulation?

While it's possible, bit manipulation offers a more efficient solution with less overhead and faster execution, especially for larger integers.

What is the time complexity of solving the "Number of Even and Odd Bits" problem?

The time complexity is O(log n), as the algorithm processes each bit of n individually.

How does GhostInterview help with the "Number of Even and Odd Bits" problem?

GhostInterview provides insights on how to leverage bit manipulation, focusing on optimizing the solution with efficient operations and counters.

terminal

Solution

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.

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

Solution 2: Bit Manipulation

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.

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

Continue Practicing

#2588 count the number of beautiful subarrays #2572 count the number of square free subsets #2571 minimum operations to reduce an integer to 0