Number of Even and Odd Bits
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This method avoids string conversion by using bitwise operations. It repeatedly checks the least significant bit (LSB) of the number n. If the LSB is 1, it increments the appropriate counter (even or odd) based on the current bit position. The number is then right-shifted to process the next bit, and the process continues until the number becomes zero.
Algorithm
- Initialize
even = 0,odd = 0, and a bit index counterindex = 0.\n2. Start a loop that continues as long asn > 0.\n3. Inside the loop, check if the least significant bit is 1 using the bitwise AND operation:(n & 1) == 1.\n4. If the LSB is 1:\n - If the currentindexis even, incrementeven.\n - Otherwise, incrementodd.\n5. Right-shiftnby one position (n >>= 1) to process the next bit.\n6. Increment theindexcounter.\n7. After the loop terminates, return the array[even, odd].
Walkthrough
This method uses bitwise operations to check each bit of the integer without converting it to a string. This is generally more efficient.\n\nThe algorithm proceeds as follows:\n- We loop as long as n is not zero.\n- In each iteration, we check the last bit of n using n & 1.\n- If it's 1, we check the current bit index's parity and update even or odd.\n- We then right-shift n by one (n >>= 1) to discard the last bit and move to the next one.\n- We increment the bit index.\n\njava\nclass Solution {\n public int[] evenOddBit(int n) {\n int even = 0;\n int odd = 0;\n int index = 0;\n while (n > 0) {\n if ((n & 1) == 1) { // Check if the last bit is 1\n if (index % 2 == 0) {\n even++;\n } else {\n odd++;\n }\n }\n n >>= 1; // Right shift to process the next bit\n index++;\n }\n return new int[]{even, odd};\n }\n}\n
Complexity
Time
O(log n), as the loop runs once for each bit in the number `n`. The number of bits is proportional to log n.
Space
O(1), as it only uses a few variables to store the counts and the index, regardless of the size of n.
Trade-offs
Pros
More efficient than the string approach in both time and space.
Works directly with the integer's binary representation.
Constant space complexity.
Cons
May be slightly less intuitive for developers not comfortable with bitwise operations.
Solutions
Solution
class Solution {public int[] evenOddBit(int n) { int[] ans = new int[2]; for (int i = 0; n > 0; n >>= 1, i ^= 1) { ans[i] += n & 1; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.