Number of Even and Odd Bits - Solution & Explanation

Problem Overview: Given an integer n, return an array where the first value is the number of set bits at even positions and the second value is the number of set bits at odd positions in the binary representation of n. Bit positions are counted from the least significant bit (LSB) starting at index 0.

Approach 1: Bit Manipulation (O(log n) time, O(1) space)

This approach processes the binary representation directly using bit operations. Repeatedly check the least significant bit with n & 1, which tells you whether the current bit is set. Track the current bit index and increment either the even or odd counter depending on its parity. After checking, right shift the number using n >>= 1 to move to the next bit.

The key insight is that every shift removes the processed bit while maintaining constant memory usage. The loop runs once for each bit in the number, which is at most log2(n). This method is efficient and avoids string conversion overhead. It’s a classic use of bit manipulation for inspecting binary structure directly.

Approach 2: String Manipulation (O(log n) time, O(log n) space)

Convert the integer into its binary string representation using functions like bin(n) in Python or Integer.toBinaryString() in Java. Iterate through the string from right to left so the least significant bit corresponds to index 0. For every character equal to '1', update either the even or odd counter depending on the index parity.

This approach is easier to visualize because you work directly with the binary digits as characters. However, it allocates additional memory for the string representation and performs extra conversions. Time complexity remains proportional to the number of bits, but space grows with the binary length. It combines string manipulation with basic binary analysis.

Recommended for interviews: The bit manipulation approach is the expected solution. It demonstrates comfort with binary operations such as & and bit shifting, both common in low-level algorithm questions. The string approach shows understanding of the problem but sacrifices constant space and efficiency. Interviewers typically prefer the direct bit-processing method because it reflects stronger control over binary representations.