2595. Number of Even and Odd Bits
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.
Which of the following is a good use case for backtracking?
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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
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:
answill be[0, 0], starting with zero counts for both even and odd indices.iwill be initialized to0since we begin with index0(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 incrementans[0]to[1, 0]. - Shift
nright by 1 (n >>= 1), n = 5 (binary101), togglei(i ^= 1), nowi = 1. - n & 1 = 1 (even, index 1), so increment
ans[1]to[1, 1]. - Shift
nright by 1, n = 2 (binary10), togglei(i ^= 1), nowi = 0. - n & 1 = 0, so no increment,
ansstays the same[1, 1]. - Shift
nright by 1, n = 1 (binary1), togglei(i ^= 1), nowi = 1. - Finally, n & 1 = 1 (odd, index 3), increment
ans[1]to[1, 2]. - Shift
nright 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
221class 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}
261#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};
201/**
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}
30In a binary min heap, the maximum element can be found in:
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.
Which data structure is used to implement priority queue?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.