Number of Even and Odd Bits - Solution & Explanation
Problem Statement
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 <= 1000
Approach Overview
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.
Approach 1: Bit Manipulation
This approach involves bit manipulation to count the number of 1s at even and odd positions in the binary representation of the number. We can achieve this by using bit shifts and checking if a bit is set (1) or not.
This C code defines a function even_odd_bits that takes an integer n and calculates the number of 1s at even and odd bit positions. It uses a bitwise AND operation to check if the current bit is set, shifts right to check the next bit, and increments counters accordingly. The result is stored in a result array.
Code
C
C++
Java
Python
C#
JavaScript
Go
TypeScript
Rust
Complexity
Time Complexity: O(log n), where n is the input number. This is due to iterating over each bit in the binary representation.
Space Complexity: O(1) as no additional space is required.
Approach 2: String Manipulation
This approach involves converting the number to its binary string representation and then iterating through the string characters to count 1s at even and odd indices based on the length of the string.
This C code converts the number to a binary string, counts '1's at even and odd positions, and outputs the counts. The binary string is built in reverse, which makes direct iteration easy for index determination.
Complexity
Time Complexity: O(log n).
Space Complexity: O(log n) due to the binary string storage.
Approach 3: Enumerate
According to the problem description, enumerate the binary representation of n from the low bit to the high bit. If the bit is 1, add 1 to the corresponding counter according to whether the index of the bit is odd or even.
The time complexity is O(log n) and the space complexity is O(1). Where n is the given integer.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation | Time Complexity: O(log n), where n is the input number. This is due to iterating over each bit in the binary representation. |
| String Manipulation | Time Complexity: O(log n). |
| Enumerate | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation | O(log n) | O(1) | Best general solution; minimal memory and direct access to bits |
| String Manipulation | O(log n) | O(log n) | Useful for readability or when already working with binary strings |
Video Solution
2595. Number of Even and Odd Bits | Weekly Contest 337 | LeetCode 2595 • Bro Coders • 960 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Even and Odd Bits easy or hard?
Number of Even and Odd Bits Python/Java solution
How to solve Number of Even and Odd Bits in O(log n)?
What is the best approach for Number of Even and Odd Bits?
Is Number of Even and Odd Bits asked at Google/Amazon/Meta?
What data structure is used in Number of Even and Odd Bits?
What is the time complexity of Number of Even and Odd Bits?
Ready to solve this problem?
Practice Number of Even and Odd Bits with our built-in code editor and test cases.
Practice on FleetCode