Leetcode 2595: Number of Even and Odd Bits

Input: The input consists of an integer `n`.

Example: For `n = 50`.

Constraints:

• 1 <= n <= 1000

Output: Return an array with two elements: the first element is the count of `1` bits at even indices and the second element is the count of `1` bits at odd indices.

Example: For `n = 50`, the output is `[1, 2]`.

Constraints:

• The output is an array of two integers.

Goal: To efficiently count the `1` bits at even and odd indices in the binary representation of `n`.

Steps:

• 1. Convert `n` to its binary representation.

• 2. Iterate through each bit of the binary representation, counting the `1` bits at even and odd indices separately.

• 3. Return the result as an array with the counts of even and odd indexed `1` bits.

Goal: The value of `n` is between 1 and 1000.

Steps:

• 1 <= n <= 1000

Assumptions:

• The binary representation of `n` will not exceed 10 bits in length.

• Input: For `n = 50`

• Explanation: The binary representation of `50` is `110010`. There is one `1` at an even index (index 1), and two `1`s at odd indices (indices 4 and 5). Thus, the output is `[1, 2]`.

Approach: The solution involves converting `n` to its binary form, then iterating through each bit, keeping track of counts of `1` bits at even and odd positions.

Observations:

• The binary representation of `n` is at most 10 bits long for values of `n` up to 1000.

• We can solve this problem by iterating through the binary representation and checking the position of each bit.

• We will use a loop to check each bit of `n` and classify it as belonging to either an even or odd index.

Steps:

• 1. Initialize two counters: one for even indexed `1` bits and one for odd indexed `1` bits.

• 2. Convert `n` to binary and iterate through each bit from right to left.

• 3. If the index of a `1` bit is even, increment the even counter. If the index is odd, increment the odd counter.

• 4. Return the results in an array.

Empty Inputs:

• The input `n` will always be a positive integer.

Large Inputs:

• The largest possible input is `n = 1000`, which is manageable within the solution's time complexity.

Special Values:

• When `n` is a small number, such as 1 or 2, the solution should still work correctly.

Constraints:

• The solution must handle all values of `n` between 1 and 1000 efficiently.

vector<int> evenOddBit(int n) {
    int a=0,b=0;
    int c=0;
    while(n>0)
    {
        if(c%2==0)
        {
            if(n%2==1)
            {
                a++;
            }
        }
        else
        {
            if(n%2==1) b++;
        }
        n=n/2;
        c++;
        
    }
    return {a,b};
}

1 : Function Definition

vector<int> evenOddBit(int n) {

Define a function that takes an integer `n` as input and returns a vector of two integers representing counts of 1's at even and odd bit positions.

2 : Variable Initialization

    int a=0,b=0;

Initialize two variables `a` and `b` to count the 1's at even and odd positions, respectively.

3 : Variable Initialization

    int c=0;

Initialize a counter `c` to keep track of the bit position.

4 : Loop

    while(n>0)

Start a while loop that continues until `n` becomes zero. This loop will iterate through the bits of the number.

5 : Condition Check

        if(c%2==0)

Check if the current bit position (`c`) is even.

6 : Increment Counter

            if(n%2==1)

Check if the current bit is 1.

7 : Increment Counter

                a++;

Increment the counter `a` for even bit positions.

8 : Else Block

        else

For odd bit positions.

9 : Increment Counter

            if(n%2==1) b++;

If the current bit is 1, increment the counter `b` for odd bit positions.

10 : Bit Shift

        n=n/2;

Right shift `n` by 1 (divide by 2) to move to the next bit.

11 : Counter Increment

        c++;

Increment the bit position counter `c`.

12 : Return Statement

    return {a,b};

Return a vector containing the counts of 1's at even and odd bit positions.

Best Case: O(b)

Average Case: O(b)

Worst Case: O(b)

Description: The time complexity is O(b), where `b` is the number of bits in `n`. Since `n <= 1000`, `b` is at most 10.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) as we only use a few integer counters to store the results.

Leetcode 2595: Number of Even and Odd Bits

Explore →