What is the brute force solution for Number of Even and Odd Bits?

The brute force approach for Number of Even and Odd Bits is Brute Force, with O(b), where b is the number of bits in the binary representation of n. time complexity and O(1) space complexity. We can convert the number to its binary representation and then iterate through each bit to count how many bits at even and odd indices are set to 1. This is straightforward but not the most efficient way. The optimal Optimal Solution approach improves this to O(b), where b is the number of bits in the binary representation of n..

What algorithm or data structure is used to solve Number of Even and Odd Bits?

Number of Even and Odd Bits uses the following concepts: Bit Manipulation. The recommended patterns to study are: Bit Manipulation, Counting Bits.

What are the interview tips for Number of Even and Odd Bits?

Explain your thought process clearly while coding. Practice bit manipulation problems to build confidence. Always consider edge cases, such as the smallest and largest inputs.

What are common mistakes when solving Number of Even and Odd Bits?

Forgetting to shift the number after checking the LSB. Confusing even and odd indices when counting.

#2595

Number of Even and Odd Bits

Easy

Bit ManipulationBit ManipulationCounting Bits

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(b), where b is the number of bits in the binary representation of n.	O(b), where b is the number of bits in the binary representation of n.
Space	O(1)	O(1)

💡

Intuition

Time O(b), where b is the number of bits in the binary representation of n.Space O(1)

Instead of converting to binary, we can use bit manipulation to directly check each bit of the number. This avoids the overhead of string conversion and is more efficient.

⚙️

Algorithm

5 steps

1Step 1: Initialize two counters, even and odd, to zero.
2Step 2: While n is greater than 0, check if the least significant bit (LSB) is 1 using n & 1.
3Step 3: If LSB is 1, check the index of the bit (using a counter) to determine if it's even or odd, and increment the respective counter.
4Step 4: Right shift n by 1 to check the next bit.
5Step 5: Repeat until n becomes 0. Return the array [even, odd].

solution.py14 lines

1# Full working Python code
2
3def countBits(n):
4    even, odd = 0, 0
5    index = 0
6    while n > 0:
7        if n & 1:
8            if index % 2 == 0:
9                even += 1
10            else:
11                odd += 1
12        n >>= 1
13        index += 1
14    return [even, odd]

ℹ

Complexity note: The time complexity remains O(b) as we still iterate through the bits of n, but we do so in a more efficient manner without converting to a string. The space complexity is O(1) since we only use a fixed amount of space.

1Understanding bit manipulation is crucial for optimizing solutions.
2Recognizing patterns in how bits are indexed can simplify counting tasks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.