LeetCode 2595 - Number of Even and Odd Bits

LeetCode Problem 2595

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to analyze the binary representation of a positive integer n and count how many 1 bits appear at even indices and how many appear at odd indices.

Bit positions are counted from right to left, starting at index 0. This means the least significant bit, the rightmost bit, is at index 0, the next bit is at index 1, and so on.

We only care about bits whose value is 1. If a bit is 0, it does not contribute to either count.

For example, if n = 50, its binary representation is 110010.

Reading from right to left:

Index	Bit
0	0
1	1
2	0
3	0
4	1
5	1

The 1 bits occur at indices 1, 4, and 5.

• Index 4 is even, so even = 1
• Indices 1 and 5 are odd, so odd = 2

The result is [1, 2].

The input consists of a single positive integer n, where:

1 <= n <= 1000

This constraint tells us the number is very small. Since 1000 in binary has only about 10 bits, even a straightforward solution would be fast enough. However, this problem belongs to the Bit Manipulation category, so the intended solution is to directly process bits efficiently.

An important guarantee is that n is always positive, meaning we never need to handle 0 or negative numbers. This simplifies the implementation because we can safely stop once n becomes 0 during bit processing.

Some edge cases are worth identifying early. A number with only one set bit, such as n = 1 or n = 2, tests whether indexing logic is correct. Numbers where all relevant bits fall into the same parity category, such as powers of two, can expose off by one mistakes. Inputs with alternating bit patterns can also reveal indexing bugs.

Approaches

Brute Force Approach

A brute force solution would first convert the integer into a binary string using something like bin(n), reverse the string so indexing matches the problem statement, and then iterate through every character.

For each bit position, we would check:

• Is the bit equal to '1'?
• Is its index even or odd?

Depending on the parity of the index, we increment either the even count or odd count.

This approach is correct because it explicitly inspects every bit and directly follows the problem definition. However, it introduces unnecessary overhead by converting the number into a string and requiring extra memory for that representation.

Although the constraints are small enough that this works perfectly fine, it is not the most natural bit manipulation solution.

Optimal Approach

The key observation is that binary digits can be processed directly using bitwise operations.

At any moment:

• n & 1 tells us whether the least significant bit is 1
• n >>= 1 removes the least significant bit by shifting all bits right

We can iterate through the bits one by one while maintaining a current index.

For each bit:

• If the least significant bit is 1, increment either the even or odd counter depending on the current index parity
• Shift n right to process the next bit
• Increase the index

This avoids string conversion entirely and uses constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log n)	O(log n)	Converts number to a binary string and scans it
Optimal	O(log n)	O(1)	Processes bits directly using bitwise operations

Algorithm Walkthrough

1. Initialize two counters, even_count and odd_count, both set to 0. These will store the number of 1 bits found at even and odd positions.
2. Initialize a variable bit_index = 0. This tracks the current position of the bit being examined.
3. While n > 0, repeatedly inspect the least significant bit. We use n & 1 because it extracts the rightmost bit efficiently.
4. If (n & 1) == 1, determine whether bit_index is even or odd:

• If bit_index % 2 == 0, increment even_count
• Otherwise, increment odd_count

5. Shift the number right using n >>= 1. This removes the current least significant bit and moves the next bit into position.
6. Increment bit_index because we are now moving to the next binary position.
7. Continue until n becomes 0, meaning all bits have been processed.
8. Return [even_count, odd_count].

Why it works

The algorithm works because each iteration processes exactly one binary digit, starting from the least significant bit, which corresponds to index 0 as required by the problem. The bit shift operation ensures that every bit is visited exactly once, and the index variable guarantees we classify each 1 bit into the correct parity group. Since every relevant bit is examined and counted correctly, the final result must be accurate.

Python Solution

from typing import List

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        even_count = 0
        odd_count = 0
        bit_index = 0

        while n > 0:
            if n & 1:
                if bit_index % 2 == 0:
                    even_count += 1
                else:
                    odd_count += 1

            n >>= 1
            bit_index += 1

        return [even_count, odd_count]

The implementation closely follows the algorithm described above.

We begin by initializing counters for even and odd indexed 1 bits. The bit_index variable keeps track of the current position as we move through the binary representation.

Inside the while loop, n & 1 checks whether the least significant bit is set. If it is, we determine whether the current index is even or odd using the modulo operator and update the appropriate counter.

After processing the current bit, n >>= 1 shifts all bits to the right, effectively discarding the bit we just handled. At the same time, bit_index is incremented so the next iteration corresponds to the next binary position.

Once n becomes 0, all bits have been processed and we return the result as a two element list.

Go Solution

func evenOddBit(n int) []int {
	evenCount := 0
	oddCount := 0
	bitIndex := 0

	for n > 0 {
		if n&1 == 1 {
			if bitIndex%2 == 0 {
				evenCount++
			} else {
				oddCount++
			}
		}

		n >>= 1
		bitIndex++
	}

	return []int{evenCount, oddCount}
}

The Go implementation mirrors the Python solution very closely. Since Go does not have Python style lists, we return a slice using []int{evenCount, oddCount}.

Bitwise operations work naturally with integers in Go, so n&1 and n >>= 1 behave exactly as expected. Integer overflow is not a concern because the constraint n <= 1000 is extremely small.

Unlike Python, there is no distinction between mutable and immutable integers here that affects implementation, and there are no concerns about nil versus empty collections because we always return a fixed size slice.

Worked Examples

Example 1

Input: n = 50

Binary representation:

110010

We process bits from right to left.

Iteration	n	n & 1	Bit Index	Action	Even	Odd
1	50	0	0	Ignore	0	0
2	25	1	1	Odd index, increment odd	0	1
3	12	0	2	Ignore	0	1
4	6	0	3	Ignore	0	1
5	3	1	4	Even index, increment even	1	1
6	1	1	5	Odd index, increment odd	1	2

Final answer:

[1, 2]

Example 2

Input: n = 2

Binary representation:

10

Iteration	n	n & 1	Bit Index	Action	Even	Odd
1	2	0	0	Ignore	0	0
2	1	1	1	Odd index, increment odd	0	1

Final answer:

[0, 1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	We process each binary digit exactly once
Space	O(1)	Only a few integer variables are used

The time complexity is O(log n) because a number n contains approximately log₂(n) bits, and each bit is processed once. Since every iteration shifts the number right by one position, the loop runs exactly once per bit.

The space complexity is O(1) because the algorithm only stores a fixed number of variables regardless of input size.

Test Cases

solution = Solution()

assert solution.evenOddBit(50) == [1, 2]  # Example 1
assert solution.evenOddBit(2) == [0, 1]   # Example 2

assert solution.evenOddBit(1) == [1, 0]   # Smallest valid input
assert solution.evenOddBit(3) == [1, 1]   # Binary: 11
assert solution.evenOddBit(4) == [1, 0]   # Binary: 100

assert solution.evenOddBit(5) == [2, 0]   # Binary: 101, both set bits at even indices
assert solution.evenOddBit(10) == [0, 2]  # Binary: 1010, both set bits at odd indices

assert solution.evenOddBit(15) == [2, 2]  # Binary: 1111, balanced even/odd
assert solution.evenOddBit(1000) == [3, 3]  # Upper constraint boundary

Test	Why
50 → [1,2]	Verifies the first provided example
2 → [0,1]	Verifies the second provided example
1 → [1,0]	Tests the smallest valid input
3 → [1,1]	Ensures mixed even and odd counting
4 → [1,0]	Tests a power of two at an even index
5 → [2,0]	Verifies multiple even indexed set bits
10 → [0,2]	Verifies multiple odd indexed set bits
15 → [2,2]	Tests all lower bits set
1000 → [3,3]	Tests the maximum constraint value

Edge Cases

One important edge case is the smallest valid input, n = 1. Since the binary representation is simply 1, there is only one set bit at index 0, which is even. A buggy implementation might incorrectly start indexing from 1, producing the wrong result. Our implementation starts at bit_index = 0, ensuring correctness.

Another important case is powers of two, such as n = 2 or n = 4. These numbers contain exactly one set bit, making them excellent tests for index accuracy. If the shifting or indexing logic is incorrect, these cases fail immediately. Because our algorithm increments bit_index after each shift, the position remains synchronized with the actual bit.

A third edge case is numbers with alternating bit patterns, such as n = 10 (1010 in binary). These values help verify that even and odd indices are classified properly. A common bug is reversing index direction or treating the leftmost bit as index 0. Since we always process from the least significant bit using n & 1, our implementation naturally follows the problem's right to left indexing rule.

Finally, values with many consecutive set bits, such as n = 15 (1111), ensure the algorithm correctly counts multiple bits across both parity groups. Since every bit is processed independently and exactly once, no counts are skipped or duplicated.