You are given a positive integer n.
Let even denote the number of even indices in the binary representation of n with value 1.
Let odd denote the number of odd indices in the binary representation of n with value 1.
Note that bits are indexed from right to left in the binary representation of a number.
Return the array [even, odd].
Example 1:
Input: n = 50
Output: [1,2]
Explanation:
The binary representation of 50 is 110010.
It contains 1 on indices 1, 4, and 5.
Example 2:
Input: n = 2
Output: [0,1]
Explanation:
The binary representation of 2 is 10.
It contains 1 only on index 1.
Constraints:
1 <= n <= 1000The key idea in #2595 Number of Even and Odd Bits is to analyze the binary representation of a number and count how many set bits (1) appear at even and odd positions. Positions are typically indexed from the least significant bit (LSB) starting at 0.
A straightforward approach is to repeatedly inspect the last bit using a bitwise AND operation (n & 1). Maintain a position counter and increment either the even or odd count whenever the extracted bit equals 1. After processing the current bit, right-shift the number (n >> 1) to move to the next position. Continue until the number becomes zero.
This technique leverages basic bit manipulation operations and avoids converting the number to a binary string. Since the number of bits in an integer is limited, the algorithm runs efficiently with minimal memory usage. The result is typically returned as a pair containing the counts of even-indexed and odd-indexed set bits.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit-by-bit iteration with shifting | O(log n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Maintain two integer variables, even and odd, to count the number of even and odd indices in the binary representation of integer n.
Divide n by 2 while n is positive, and if n modulo 2 is 1, add 1 to its corresponding variable.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
While this exact problem may not always appear, similar bit manipulation questions are common in technical interviews. Practicing problems like this helps strengthen understanding of binary operations and bitwise techniques frequently tested in coding rounds.
Bit manipulation allows direct access to individual bits of a number without converting it into a binary string. This keeps the solution faster and more memory efficient while aligning with common interview expectations for low-level operations.
No complex data structure is required for this problem. Simple integer variables to track the position and counts of even and odd set bits are sufficient, making the solution very space efficient.
The optimal approach is to iterate through the binary representation of the number using bit manipulation. By checking the least significant bit with n & 1 and shifting right each step, you can count set bits at even and odd positions efficiently in O(log n) time.