Problem Description

You are given a positive integer n. Your task is to count how many 1 bits appear at even positions and how many appear at odd positions in the binary representation of n.

The binary representation is indexed from right to left, starting at index 0. This means:

• The rightmost bit (least significant bit) is at index 0 (even)
• The second bit from the right is at index 1 (odd)
• The third bit from the right is at index 2 (even)
• And so on...

You need to:

1. Count all the 1 bits that appear at even indices (0, 2, 4, ...) - store this as even
2. Count all the 1 bits that appear at odd indices (1, 3, 5, ...) - store this as odd
3. Return the result as an array [even, odd]

For example, if n = 13:

• Binary representation: 1101
• Index positions (right to left): indices 3, 2, 1, 0 correspond to bits 1, 1, 0, 1
• Bits at even indices (0, 2): both are 1, so even = 2
• Bits at odd indices (1, 3): index 1 has 0 and index 3 has 1, so odd = 1
• Return [2, 1]

The solution iterates through each bit of n from right to left. It uses n & 1 to check if the current least significant bit is 1, adds it to the appropriate counter based on whether the current position is even or odd (tracked by variable i which alternates between 0 and 1 using XOR operation), then shifts n right by one position to process the next bit.

Intuition

The key insight is that we need to process the binary representation of n bit by bit, keeping track of whether each bit position is even or odd.

Since we're indexing from right to left starting at 0, we can process the number from its least significant bit (rightmost) to its most significant bit (leftmost). This naturally aligns with how we can extract bits from a number using bitwise operations.

The most straightforward way to extract bits one by one is:

1. Use n & 1 to get the current least significant bit (0 or 1)
2. Use n >> 1 to shift the number right, making the next bit become the least significant bit

As we process each bit, we need to know if we're at an even or odd index. Instead of maintaining a separate counter that we increment and check with modulo operation (index % 2), we can use a clever alternating pattern. We start with index 0 (even), then 1 (odd), then 0 (even), and so on.

This alternating pattern can be elegantly achieved using XOR: i ^= 1. Starting with i = 0:

• 0 ^ 1 = 1 (switches to odd)
• 1 ^ 1 = 0 (switches back to even)
• This continues alternating between 0 and 1

By using ans[i] where i alternates between 0 and 1, we automatically add to ans[0] (even count) when at even positions and ans[1] (odd count) when at odd positions. The value n & 1 gives us either 0 or 1, which is exactly what we want to add to our counter.

The loop continues until n becomes 0, meaning we've processed all the bits that were set to 1 (we don't need to count leading zeros).

Solution Approach

The solution uses a bit manipulation approach to enumerate through the binary representation of n from the least significant bit to the most significant bit.

Implementation Steps:

1. Initialize counters: Create an array ans = [0, 0] where ans[0] will store the count of 1s at even indices and ans[1] will store the count of 1s at odd indices.

2. Set position tracker: Initialize i = 0 to track whether we're currently at an even (0) or odd (1) position.

3. Process bits iteratively: Use a while loop that continues as long as n > 0:

   a. Extract current bit: Use n & 1 to get the least significant bit. This operation returns 1 if the bit is set, 0 otherwise.

   b. Update counter: Add the extracted bit value to ans[i]. Since i alternates between 0 and 1, this automatically adds to the correct counter:

   • When i = 0, we add to the even counter
   • When i = 1, we add to the odd counter

   c. Toggle position: Use i ^= 1 to flip between even (0) and odd (1) positions. The XOR operation with 1 toggles the value:

   • 0 ^ 1 = 1
   • 1 ^ 1 = 0

   d. Shift to next bit: Use n >>= 1 to right-shift n by one position, effectively removing the processed bit and bringing the next bit to the least significant position.

4. Return result: Once all bits are processed (when n becomes 0), return the ans array containing [even_count, odd_count].

Example walkthrough with n = 13 (binary: 1101):

• Initial: ans = [0, 0], i = 0, n = 1101
• Iteration 1: bit = 1, ans[0] += 1 → ans = [1, 0], i = 1, n = 110
• Iteration 2: bit = 0, ans[1] += 0 → ans = [1, 0], i = 0, n = 11
• Iteration 3: bit = 1, ans[0] += 1 → ans = [2, 0], i = 1, n = 1
• Iteration 4: bit = 1, ans[1] += 1 → ans = [2, 1], i = 0, n = 0
• Return [2, 1]

The time complexity is O(log n) as we process each bit of n, and the space complexity is O(1) as we only use a fixed-size array and a few variables.

Example Walkthrough

Let's walk through the solution with n = 23 (binary: 10111).

We'll track the binary representation from right to left with indices:

Binary:  1   0   1   1   1
Index:   4   3   2   1   0
Type:   even odd even odd even

Initial Setup:

• ans = [0, 0] where ans[0] counts 1s at even positions, ans[1] counts 1s at odd positions
• i = 0 (starting at even position)
• n = 23 (binary: 10111)

Iteration 1:

• Current bit: n & 1 = 10111 & 1 = 1 (rightmost bit)
• Position: i = 0 (even), so we add to ans[0]
• Update: ans[0] += 1 → ans = [1, 0]
• Toggle position: i ^= 1 → i = 1
• Shift right: n >>= 1 → n = 1011

Iteration 2:

• Current bit: n & 1 = 1011 & 1 = 1
• Position: i = 1 (odd), so we add to ans[1]
• Update: ans[1] += 1 → ans = [1, 1]
• Toggle position: i ^= 1 → i = 0
• Shift right: n >>= 1 → n = 101

Iteration 3:

• Current bit: n & 1 = 101 & 1 = 1
• Position: i = 0 (even), so we add to ans[0]
• Update: ans[0] += 1 → ans = [2, 1]
• Toggle position: i ^= 1 → i = 1
• Shift right: n >>= 1 → n = 10

Iteration 4:

• Current bit: n & 1 = 10 & 1 = 0
• Position: i = 1 (odd), so we add to ans[1]
• Update: ans[1] += 0 → ans = [2, 1] (no change since bit is 0)
• Toggle position: i ^= 1 → i = 0
• Shift right: n >>= 1 → n = 1

Iteration 5:

• Current bit: n & 1 = 1 & 1 = 1
• Position: i = 0 (even), so we add to ans[0]
• Update: ans[0] += 1 → ans = [3, 1]
• Toggle position: i ^= 1 → i = 1
• Shift right: n >>= 1 → n = 0

Result:

• Loop ends since n = 0
• Return [3, 1]

This matches our expectation: positions 0, 2, and 4 (even) have 1s, while only position 1 (odd) has a 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm iterates through each bit of the binary representation of n. In each iteration:

• It checks the least significant bit using n & 1 - O(1) operation
• It toggles the index using i ^= 1 - O(1) operation
• It right shifts n by 1 position using n >>= 1 - O(1) operation

The while loop continues until n becomes 0, which happens after processing all bits in the binary representation of n. Since an integer n has ⌊log₂ n⌋ + 1 bits in its binary representation, the loop runs O(log n) times.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• ans list with exactly 2 elements - O(1)
• Variable i to track the current index - O(1)

The space usage doesn't grow with the input size n, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Index Direction

Pitfall: A common mistake is assuming the binary representation is indexed from left to right (most significant bit first). This leads to incorrect counting as developers might process the bits in the wrong order or assign them to wrong position categories.

Example of incorrect approach:

# WRONG: Converting to string and indexing from left
binary_str = bin(n)[2:]  # "1101" for n=13
for i, bit in enumerate(binary_str):
    if bit == '1':
        if i % 2 == 0:
            even += 1  # This incorrectly treats leftmost bit as index 0

Solution: Always remember that bit positions are counted from right to left (LSB to MSB). The rightmost bit is at index 0. Using bit manipulation with right shift ensures correct processing order.

2. Incorrect Position Tracking Initialization

Pitfall: Starting the position index at 1 instead of 0, thinking the first position should be 1-indexed.

Example of incorrect code:

position_index = 1  # WRONG: Should start at 0 for even position
while n > 0:
    result[position_index] += n & 1
    position_index ^= 1
    n >>= 1

Solution: Initialize position_index = 0 since the rightmost bit (LSB) is at index 0, which is an even position.

3. Using Modulo Instead of XOR for Position Toggle

Pitfall: While using position_index = (position_index + 1) % 2 works correctly, it's less efficient than XOR and might lead to confusion or errors if modified incorrectly.

Less optimal approach:

position_index = 0
while n > 0:
    result[position_index] += n & 1
    position_index = (position_index + 1) % 2  # Works but less efficient
    n >>= 1

Solution: Use position_index ^= 1 for cleaner and more efficient toggling between 0 and 1.

4. Off-by-One Error in Result Array

Pitfall: Confusing the array indices with the actual even/odd positions, potentially swapping the results.

Example of confusion:

# Accidentally returning [odd_count, even_count] instead of [even_count, odd_count]
result = [0, 0]
# ... processing logic ...
return [result[1], result[0]]  # WRONG: Swapped order

Solution: Maintain clear variable naming and remember that result[0] stores even position counts and result[1] stores odd position counts. The position_index directly corresponds to the array index.

5. Forgetting Edge Cases

Pitfall: Not considering that n could be 0 (though the problem states positive integer) or very large numbers.

Solution: The current implementation handles all positive integers correctly. If extending to handle 0, the function would correctly return [0, 0] without modification.