Teaching Kids Programming – Count Number of Even and Odd Bits (Binary)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a positive integer n. Let even denote the number of even indices in the binary representation of n (0-indexed) with value 1. Let odd denote the number of odd indices in the binary representation of n (0-indexed) with value 1. Return an integer array answer where answer = [even, odd].

Example 1:
Input: n = 17
Output: [2,0]
Explanation: The binary representation of 17 is 10001.
It contains 1 on the 0th and 4th indices.
There are 2 even and 0 odd indices.

Example 2:
Input: n = 2
Output: [0,1]
Explanation: The binary representation of 2 is 10.
It contains 1 on the 1st index.
There are 0 even and 1 odd indices.

Constraints:
1 <= n <= 1000

Algorithm to Count the Number of Even and Odd Bits (Binary)

Hello fellow coders! In this blog post, we will dive deep into a solution for the LeetCode problem 2595, analyzing the given Python code. The goal is to help you understand not just the code, but the underlying logic and the problem itself.

Problem Statement:
For the given problem, we have to compute the number of set bits (1s) in even and odd positions for a given integer n. The least significant bit (LSB) is considered at position 0.

Python Solution Breakdown:

1
2
3
4
5
6
7
8
9

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        ans = [0, 0]        
        i = 0
        while n:
            ans[i] += n & 1
            n >>= 1
            i = 1 - i
        return ans 

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        ans = [0, 0]        
        i = 0
        while n:
            ans[i] += n & 1
            n >>= 1
            i = 1 - i
        return ans 

Here’s a step-by-step breakdown of the solution:

Initialization:

1

ans = [0, 0]

ans = [0, 0]

ans is initialized with two zeros. It will store the count of 1s in odd and even positions. Specifically, ans[0] is for even positions and ans[1] is for odd positions.

1

i = 0

i = 0

i will keep track of whether we’re currently at an even or odd position.

Iterate while n is not zero:

1

while n:

while n:

This loop runs as long as n is not zero. In each iteration, we process one bit of n.

Extract the last bit and add to the answer:

1

ans[i] += n & 1

ans[i] += n & 1

The expression (n & 1) fetches the least significant bit of n. If the LSB is 1, it’s added to the count of either ans[0] (even position) or ans[1] (odd position), based on the value of i.

Right shift n to process the next bit:

1

n >>= 1

n >>= 1

The right shift operation >> shifts the bits of n to the right, effectively removing the last bit and moving the next bit into the least significant position.

Toggle the value of i to switch between even and odd positions:

1

i = 1 - i

i = 1 - i

This simple arithmetic trick toggles i between 0 and 1. If i is currently 0 (even position), it becomes 1 (odd position), and vice versa.

Return the result:

1

return ans

return ans

Finally, once the while loop ends (i.e., all bits of n have been processed), we return the ans list.

The time complexity is O(LogN) and the space complexity is O(1).

Conclusion:

This solution uses bit manipulation techniques, specifically the bitwise AND and the right shift operations, to efficiently compute the number of set bits in even and odd positions of an integer. Understanding how this code works helps in honing skills in bitwise operations, a crucial tool for many competitive coding problems. Happy coding!

–EOF (The Ultimate Computing & Technology Blog) —