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.
This approach converts the integer n into its binary string representation. It then iterates through this string from right to left, keeping track of the current bit's index (0-based). If a '1' is found, it checks if the index is even or odd and increments the corresponding counter.
Algorithm
- Convert the input integer
nto its binary string representation usingInteger.toBinaryString(n).\n2. Initialize two counters,evenandodd, to zero.\n3. Iterate fromi = 0up to the length of the binary string. Thisiwill represent the bit index from the right.\n4. In each iteration, access the character corresponding to thei-th bit from the right.\n5. If the character is '1':\n - Ifiis even, incrementeven.\n - Ifiis odd, incrementodd.\n6. After the loop, return the result as an array[even, odd].
Walkthrough
This approach converts the integer to a string and iterates over it. The main steps are:\n- Convert n to its binary string representation.\n- Iterate through the string from right to left, which corresponds to indices 0, 1, 2, ...\n- For each '1' encountered, check the parity of its index and update the respective counter.\n\njava\nclass Solution {\n public int[] evenOddBit(int n) {\n String binaryString = Integer.toBinaryString(n);\n int even = 0;\n int odd = 0;\n int len = binaryString.length();\n // Iterate from right to left of the string\n // The index from the right is `i`\n for (int i = 0; i < len; i++) {\n // Character at index `len - 1 - i` corresponds to bit position `i`\n if (binaryString.charAt(len - 1 - i) == '1') {\n if (i % 2 == 0) { // Even index\n even++;\n } else { // Odd index\n odd++;\n }\n }\n }\n return new int[]{even, odd};\n }\n}\n
Complexity
Time
O(log n), where n is the input integer. This is because converting n to a binary string takes O(log n) time, and iterating through the string of length log n also takes O(log n) time.
Space
O(log n) to store the binary string representation of n.
Trade-offs
Pros
Simple to understand and implement.
Leverages standard library functions for string conversion.
Cons
Less efficient due to the overhead of string creation and manipulation.
Requires extra space proportional to the number of bits in n.
This is the most efficient approach, leveraging bitmasking to isolate all even-indexed and odd-indexed bits at once. It uses a mask 0x55555555 (binary 0101...) to get the set bits at even positions and a mask 0xAAAAAAAA (binary 1010...) for odd positions. After applying the masks, the number of set bits (population count) in each result is calculated using a highly optimized built-in function like Integer.bitCount().
Algorithm
- Define a mask for even positions:
evenMask = 0x55555555.\n2. Define a mask for odd positions:oddMask = 0xAAAAAAAA.\n3. Calculate the bits at even positions byn & evenMask.\n4. Count the number of set bits in the result usingInteger.bitCount()to get theevencount.\n5. Calculate the bits at odd positions byn & oddMask.\n6. Count the number of set bits in this result usingInteger.bitCount()to get theoddcount.\n7. Return the counts as[even, odd].
Walkthrough
This highly efficient approach uses bitmasks to isolate all even-indexed and odd-indexed bits simultaneously. Then, it uses a built-in function to count the set bits in the masked results.\n\n- The mask 0x55555555 in binary is 01010101.... When ANDed with n, it keeps only the bits at even positions (0, 2, 4, ...).\n- The mask 0xAAAAAAAA in binary is 10101010.... When ANDed with n, it keeps only the bits at odd positions (1, 3, 5, ...).\n- Integer.bitCount() is a hardware-accelerated instruction on many platforms that counts the number of 1s in an integer's binary representation very quickly.\n\njava\nclass Solution {\n public int[] evenOddBit(int n) {\n // Mask for even indices: 01010101...\n int evenMask = 0x55555555; \n // Mask for odd indices: 10101010...\n int oddMask = 0xAAAAAAAA;\n \n int evenCount = Integer.bitCount(n & evenMask);\n int oddCount = Integer.bitCount(n & oddMask);\n \n return new int[]{evenCount, oddCount};\n }\n}\n
Complexity
Time
O(1). The bitwise AND operations are single-cycle instructions. The `Integer.bitCount()` method is often implemented using a dedicated hardware instruction (`POPCNT`) or a fast bit-twiddling algorithm, making it effectively constant time for a fixed-size integer (e.g., 32-bit).
Space
O(1). This approach uses only a fixed number of variables, resulting in constant space usage.
Trade-offs
Pros
Extremely fast and efficient, with constant time complexity.
Elegant and concise for those familiar with bit manipulation.
Cons
The 'magic numbers' (masks) can be obscure without explanation.
Relies on a specific built-in function (
Integer.bitCount()) which, while standard, abstracts away the counting logic.
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; }}class Solution: def evenOddBit(self, n: int) -> List[int]: ans = [0, 0] i = 0 while n: ans[i] += n & 1 i ^= 1 n >>= 1 return ansclass Solution {public: vector<int> evenOddBit(int n) { vector<int> ans(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.