Difficulty: Easy | Acceptance: 73.50% | Paid: No Topics: Bit Manipulation
You are given a positive integer n.
Return an array answer where answer[0] is the number of even-numbered bits set to 1 in the binary representation of n and answer[1] is the number of odd-numbered bits set to 1 in the binary representation of n.
The 0th bit is considered even.
- Examples
- Constraints
- Bit Manipulation with Shifting
- Bit Manipulation with Masking
- String Conversion
Examples
Input: n = 17
Output: [2,0]
Explanation: The binary representation of 17 is 10001.
- The 0th and 4th bits are set to 1 (both are even-numbered bits).
- The 1st, 2nd, and 3rd bits are set to 0.
- So answer[0] = 2 and answer[1] = 0.
Input: n = 2
Output: [0,1]
Explanation: The binary representation of 2 is 10.
- The 0th bit is set to 0.
- The 1st bit is set to 1 (odd-numbered bit).
- So answer[0] = 0 and answer[1] = 1.
Constraints
1 <= n <= 1000
Bit Manipulation with Shifting
Intuition Iterate through each bit position by right-shifting the number, checking if the least significant bit is set, and incrementing the appropriate counter based on position parity.
Steps
- Initialize counters for even and odd positions
- While n is greater than 0, check if the least significant bit is set using bitwise AND
- If set, increment even or odd counter based on current position
- Right-shift n and increment position counter
- Return the result array
class Solution:
def evenOddBit(self, n: int) -> list[int]:
even = odd = 0
pos = 0
while n:
if n & 1:
if pos % 2 == 0:
even += 1
else:
odd += 1
n >>= 1
pos += 1
return [even, odd]Complexity
- Time: O(log n) - we process each bit of n
- Space: O(1) - only using constant extra space
- Notes: Simple and intuitive approach with minimal operations
Bit Manipulation with Masking
Intuition Use bitmask patterns to extract all even-positioned bits and odd-positioned bits separately, then count the set bits in each result.
Steps
- Create mask for even positions (0x55555555 = 01010101… in binary)
- Create mask for odd positions (0xAAAAAAAA = 10101010… in binary)
- Apply masks to n using bitwise AND to isolate even and odd bits
- Count the number of set bits in each masked result
- Return the counts as an array
class Solution:
def evenOddBit(self, n: int) -> list[int]:
even_mask = 0x55555555 # 01010101... in binary
odd_mask = 0xAAAAAAAA # 10101010... in binary
even_bits = n & even_mask
odd_bits = n & odd_mask
# Count set bits
even_count = bin(even_bits).count('1')
odd_count = bin(odd_bits).count('1')
return [even_count, odd_count]Complexity
- Time: O(log n) - bit counting takes time proportional to number of set bits
- Space: O(1) - only using constant extra space
- Notes: Elegant solution using bitmask patterns, efficient for sparse bit patterns
String Conversion
Intuition Convert the number to its binary string representation, reverse it so the least significant bit is at index 0, then iterate through characters counting 1s at even and odd indices.
Steps
- Convert n to binary string representation
- Reverse the string so index 0 corresponds to the 0th bit (LSB)
- Iterate through each character in the reversed string
- If character is ‘1’, increment even or odd counter based on index
- Return the result array
class Solution:
def evenOddBit(self, n: int) -> list[int]:
binary = bin(n)[2:] # Remove '0b' prefix
binary = binary[::-1] # Reverse to have LSB at index 0
even = odd = 0
for i, bit in enumerate(binary):
if bit == '1':
if i % 2 == 0:
even += 1
else:
odd += 1
return [even, odd]Complexity
- Time: O(log n) - converting to binary and iterating through bits
- Space: O(log n) - storing the binary string representation
- Notes: More readable but uses extra space for string storage