Number Of Even And Odd Bits - Leetcode Solution

Problem:

Given a positive integer, count the number of even and odd bits in its binary representation.

Solution:

To solve this problem, we need to understand the binary representation of a number. In the binary representation of a number, each digit can be either 0 or 1. The rightmost digit represents the 1's place, the second-rightmost digit represents the 2's place, and so on.

An even number in binary representation has the rightmost bit as 0, and an odd number has the rightmost bit as 1. Therefore, we can count the number of even and odd bits in a number by checking the rightmost bit of the binary representation and incrementing the corresponding counter.

To obtain the binary representation of a number, we can use a bitwise AND operation with the number and 1. If the result is 1, then the rightmost bit is 1, otherwise, it is 0. We can then shift the number right by one bit to obtain the next bit until the number becomes 0.

Here is the step-by-step solution:

1. Initialize two counters, even_bits and odd_bits, to 0.
2. Obtain the binary representation of the given number by using a loop that checks the rightmost bit and shifts the number right by one bit.
3. If the rightmost bit is 1, increment the odd_bits counter, otherwise, increment the even_bits counter.
4. Repeat steps 2-3 until the number becomes 0.
5. Return both even_bits and odd_bits.

Here is the Python code for the solution:

class Solution:
    def countBits(self, num: int) -> List[int]:
        even_bits = 0
        odd_bits = 0
        
        while num:
            if num & 1:
                odd_bits += 1
            else:
                even_bits += 1
                
            num >>= 1
        
        return [even_bits, odd_bits]

Time Complexity: O(log n)

Space Complexity: O(1)

Note: This solution can be further optimized by using the Brian Kernighan Algo to count the set bits in a number, which reduces the time complexity to O(set bits). However, since we are only interested in even and odd bits, this optimization is not necessary.

1