2595. Number of Even and Odd Bits

EasyBit Manipulation

Problem Description

This problem requires us to examine the binary representation of a given positive integer n. Specifically, we need to count the number of bits set to 1 that are located at even and odd indices separately in this representation. Indices are 0-indexed, meaning they start counting from zero, and the least significant bit is at index 0. The ultimate goal is to return an array with two numbers: the first is the count of 1s at even indices, and the second is the count of 1s at odd indices in the binary representation of n.

Intuition

To solve this problem, we take advantage of bitwise operations. The key operations are & 1 to check whether the least significant bit is 1 and shifting right >> to move to the next bit. We alternate between even and odd index checks by toggling a variable i. When i is 0, which corresponds to an even index, we check and possibly increment our even count. When i is 1, for an odd index, we check and possibly increment our odd count. Each right shift (>> 1) effectively moves to the next higher bit, emulating traversal through the indices of the binary representation. This process continues until all bits have been checked, that is, until n becomes 0. The solution is both efficient, as it has a time complexity directly tied to the number of bits set in n, and straightforward, relying on fundamental bit manipulation techniques.

Solution Approach

The solution is implemented using a simple while loop, an array to keep track of the counts of 1s at even and odd indices, and a variable i to alternate between even and odd. The initial setup defines an array ans initialized to [0, 0], representing the counts at even and odd indices respectively.

The i variable is initialized to 0, which will help us toggle between even (0) and odd (1) positions. In every iteration of the while loop, the expression n & 1 is evaluated, which uses the bitwise AND operation to check if the least significant bit of n is set to 1. If it is, ans[i] is incremented, effectively counting the 1 for the current index.

We use the expression i ^= 1 to toggle the value of i between 0 and 1. This is a bitwise XOR operation which flips i from 0 to 1 or from 1 to 0, aligning with the even and odd index we are currently at.

Then, n >>= 1 shifts the binary representation of n to the right by one, essentially moving to the next bit in the binary representation of the number as the next least significant bit to check.

This loop continues until n becomes 0, meaning all bits have been processed. At the end of the loop, ans contains the counts of 1s at even and odd indices, and it is returned as the final result.

Using bitwise operations makes the algorithm efficient since it operates directly on the binary representation of the number. The space complexity is O(1) because we only use a fixed-size array and a few variables, and the time complexity is O(log n) due to the number of bits in n.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to illustrate how the solution approach works. Assume we have the positive integer n = 11. In binary, 11 is represented as 1011.

Now, let's initialize our solution:

ans will be [0, 0], starting with zero counts for both even and odd indices.
i will be initialized to 0 since we begin with index 0 (even).

We'll go through the number bit by bit, checking if each bit is a 1 and then increment the corresponding count in ans:

n = 11 (binary 1011), n & 1 = 1 (odd, index 0), so increment ans[0] to [1, 0].
Shift n right by 1 (n >>= 1), n = 5 (binary 101), toggle i (i ^= 1), now i = 1.
n & 1 = 1 (even, index 1), so increment ans[1] to [1, 1].
Shift n right by 1, n = 2 (binary 10), toggle i (i ^= 1), now i = 0.
n & 1 = 0, so no increment, ans stays the same [1, 1].
Shift n right by 1, n = 1 (binary 1), toggle i (i ^= 1), now i = 1.
Finally, n & 1 = 1 (odd, index 3), increment ans[1] to [1, 2].
Shift n right by 1, now n = 0. The loop ends.

Thus, in the binary representation of the number 11, there is 1 bit set at even indices (index 0) and 2 bits set at odd indices (indices 1 and 3). Therefore, the final ans array is [1, 2], which is the result we return.

Solution Implementation

1class Solution:
2    def even_odd_bit(self, n: int) -> List[int]:
3        # Initialize an array with two elements, for even and odd bit counts.
4        bit_counts = [0, 0]
5
6        # Initialize the index to point at the even position.
7        index = 0
8      
9        # Loop until all bits are processed.
10        while n:
11            # Add the least significant bit (LSB) to the appropriate count (even/odd).
12            bit_counts[index] += n & 1
13          
14            # Toggle index: 0 becomes 1, 1 becomes 0. (Switch between even and odd).
15            index ^= 1
16          
17            # Right shift 'n' to process the next bit.
18            n >>= 1
19
20        # Return the counts of even and odd position bits.
21        return bit_counts
22

1class Solution {
2
3    /**
4     * This method calculates the number of set bits (1s) present in the even and odd positions
5     * of the binary representation of a given number.
6     *
7     * @param n The integer whose binary representation is to be analyzed.
8     * @return An array of two integers where the first element is the count of set bits at
9     *         even positions, and the second element is the count of set bits at odd positions.
10     */
11    public int[] evenOddBit(int n) {
12        // Initializing an array to hold the count of set bits at even and odd positions
13        int[] countOfSetBits = new int[2];
14      
15        // Iterating over each bit of the input number
16        for (int i = 0; n > 0; n >>= 1, i ^= 1) {
17            // Increment the count at index 'i' where 0 refers to even and 1 refers to odd positions
18            // The current bit is determined by 'n & 1', adding to the respective count based on the position
19            countOfSetBits[i] += n & 1; // If the current bit is 1, add to the count
20        }
21      
22        // Returning the array with counts of set bits at even and odd positions
23        return countOfSetBits;
24    }
25}
26

1#include <vector> // Include the vector header for using the std::vector container.
2
3class Solution {
4public:
5    // Function that returns the count of even and odd positioned bits set to '1' in the binary representation of n.
6    std::vector<int> evenOddBit(int n) {
7        std::vector<int> ans(2); // Create a vector with 2 elements initialized to 0 to store the counts.
8        // ans[0] will hold the count of bits set in odd positions.
9        // ans[1] will hold the count of bits set in even positions.
10
11        // Loop over each bit of the integer 'n'.
12        for (int i = 0; n > 0; n >>= 1, i ^= 1) { // i flips between 0 and 1 to represent even and odd positioning.
13            ans[i] += n & 1; // Increment the count for even or odd index based on the current bit (0 or 1).
14        }
15      
16        // Return the result vector containing the counts of set bits at even and odd positions.
17        return ans;
18    }
19};
20

1/**
2 * Calculates the sum of bits at even and odd positions of a binary representation of a number.
3 * @param n - The input number to evaluate.
4 * @returns An array where the first element is the sum of bits at even positions, and the second is the sum at odd positions.
5 */
6function evenOddBit(n: number): number[] {
7    // Initialize an array with two elements set to zero.
8    // The first element is for sum of bits at even positions, and
9    // the second is for sum of bits at odd positions.
10    const bitSums = new Array(2).fill(0);
11  
12    // Initialize an index variable to toggle between 0 (even) and 1 (odd).
13    let index = 0;
14  
15    // Iterate through each bit of the number.
16    while (n > 0) {
17        // Add the current bit to the corresponding position sum.
18        bitSums[index] += n & 1;
19      
20        // Right shift the number to process the next bit.
21        n >>= 1;
22      
23        // Toggle the index between 0 and 1.
24        index ^= 1;
25    }
26  
27    // Return the array containing sums of even and odd positioned bits.
28    return bitSums;
29}
30

Time and Space Complexity

The function evenOddBit computes the number of set bits at even and odd positions in the binary representation of a given integer n. To analyze the number of operations, it iterates bit by bit through the entire binary representation of n, which in the worst case has a length of O(log n). In each iteration, it performs a constant number of operations: a bitwise AND (&), bitwise XOR (^), assignment, and right shift (>>). Therefore, the time complexity is O(log n), as with each bit operation, we move one bit position to the right until we have shifted through all the bits.

The space complexity is determined by the amount of extra space the algorithm uses besides the input. Here, the extra space used is for the variable i and the fixed-size list ans. Since the size of the list ans does not depend on the size of the input integer n and is always a list of two elements, the space complexity is constant. The space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know