Jobs

Interviews

Discussions

Number of Even and Odd Bits

Easy

Asked by:

34 views

Topics:

Bit Manipulation

You are given a positive integer n.

Let even denote the number of even indices in the binary representation of n with value 1.

Let odd denote the number of odd indices in the binary representation of n with value 1.

Note that bits are indexed from right to left in the binary representation of a number.

Return the array [even, odd].

Example 1:

Input: n = 50

Output: [1,2]

Explanation:

The binary representation of 50 is 110010.

It contains 1 on indices 1, 4, and 5.

Example 2:

Input: n = 2

Output: [0,1]

Explanation:

The binary representation of 2 is 10.

It contains 1 only on index 1.

Constraints:

1 <= n <= 1000

Try coding it in LeetCode

Number of Even and Odd Bits

Easy

Asked by:

34 views

Topics:

Bit Manipulation

You are given a positive integer n.

Let even denote the number of even indices in the binary representation of n with value 1.

Let odd denote the number of odd indices in the binary representation of n with value 1.

Note that bits are indexed from right to left in the binary representation of a number.

Return the array [even, odd].

Example 1:

Input: n = 50

Output: [1,2]

Explanation:

The binary representation of 50 is 110010.

It contains 1 on indices 1, 4, and 5.

Example 2:

Input: n = 2

Output: [0,1]

Explanation:

The binary representation of 2 is 10.

It contains 1 only on index 1.

Constraints:

1 <= n <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type and range of the input number n? Can n be negative?
How many bits are considered for determining even and odd positions? Is it limited by the integer size of the input, or is there an upper bound?
If the binary representation of 'n' has fewer bits than the positions we are considering (e.g., fewer than 2 bits), how should I handle the missing bits? Should I treat them as 0?
Are we guaranteed that 'n' is a valid integer, or do I need to handle potential invalid input or null/empty cases?
What is the expected return type? Should I return a list/array of two integers, or some other data structure to represent the count of even and odd bits?

Brute Force Solution

Approach

The problem requires us to examine the individual bits of a given number. A brute force approach involves inspecting each bit one by one to determine if it's even, odd, and whether it is a 0 or a 1.

Here's how the algorithm would work step-by-step:

Start with the rightmost bit of the number.
Check if this bit is a 0 or a 1.
Determine if this bit is at an even or odd position, starting from the right and counting from zero.
Keep track of the counts of even-positioned bits that are 1 and odd-positioned bits that are 1.
Move to the next bit to the left and repeat steps 2-4.
Continue this process until you have checked all bits of the number.
Finally, you will have the counts of even bits and odd bits that are set to 1.

Code Implementation

def count_even_odd_bits(number):
    even_bits_count = 0
    odd_bits_count = 0
    bit_position = 0

    # Iterate through bits until the number becomes zero
    while number > 0:
        # Check if the current bit is set (equal to 1)
        if number % 2 == 1:

            # Increment even/odd counts based on bit position
            if bit_position % 2 == 0:
                even_bits_count += 1

            else:
                odd_bits_count += 1

        # Shift the number to the right by one bit
        number = number // 2

        # Update the current bit position
        bit_position += 1

    return [even_bits_count, odd_bits_count]

Big(O) Analysis

Time Complexity

O(log n) – The solution iterates through the bits of the input number 'n'. The number of bits required to represent a number 'n' is proportional to log base 2 of n (log₂n). Therefore, the loop iterates approximately log₂n times, checking each bit. Each bit check takes constant time. Hence, the time complexity is O(log n).

Space Complexity

O(1) – The provided steps outline a bitwise operation approach. We only store two integer variables: one to count even bits, and another to count odd bits. The number of bits in the input number N does not affect the space used by these counters. Therefore, the space complexity is constant.

Optimal Solution

Approach

We need to find which bits in a number are 'on' (equal to 1) at even and odd places. The clever trick is to look at each bit's position directly without converting it into a list or other data structure.

Here's how the algorithm would work step-by-step:

Think of the number as a series of bits lined up from right to left, starting with the rightmost bit as position 1.
Go through each bit from right to left.
Check the position of the bit. If the position is odd, and the bit is 'on' (equal to 1), count it as an odd bit.
If the position is even, and the bit is 'on' (equal to 1), count it as an even bit.
Keep track of the counts for even and odd bits as you go.
After checking all bits, you will have the total number of even and odd bits that are 'on'.

Code Implementation

def number_of_even_and_odd_bits(number):
    even_bit_count = 0
    odd_bit_count = 0
    bit_position = 1

    # Iterate through the bits of the number
    while number > 0:

        # Check if the current bit is set (equal to 1)
        if number & 1:

            # Increment counters based on bit position
            if bit_position % 2 == 0:
                #Even position
                even_bit_count += 1

            else:
                #Odd position
                odd_bit_count += 1

        # Move to the next bit by right-shifting
        number >>= 1

        # Update position counter
        bit_position += 1

    return [even_bit_count, odd_bit_count]

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through the bits of the input integer. The number of bits in an integer is fixed and determined by the size of the data type (e.g., 32 bits for a 32-bit integer or 64 bits for a 64-bit integer). Therefore, the number of iterations is constant, regardless of the magnitude of the input number. Since the number of operations does not scale with the input, the time complexity is O(1).

Space Complexity

O(1) – The algorithm uses only two integer variables to store the counts of even and odd bits. The amount of space required for these variables does not depend on the size of the input number, N. No additional data structures are created or used during the process. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Negative input number	Convert the input number to its absolute value, as bit positions are the same for positive and negative representations of the same magnitude.
Input is zero	Return [0,0] since zero has no set bits.
Large input number close to the maximum integer value	Ensure the solution correctly handles all bits without integer overflow issues; use bitwise operations carefully.
Input is a power of 2	The solution should correctly identify one odd bit and zero even bits.
Input is a number with alternating 0s and 1s in its binary representation	The solution must accurately count the number of even and odd bits when there is a mix of both.
Integer overflow when calculating number of bits	Use bitwise operations and avoid arithmetic operations that could lead to overflow.
All bits are 1	The solution needs to count all even and odd positions correctly.
Integer with many trailing zeros	The bitwise and shifting operations are efficient at skipping over trailing zeros, thus handling this case efficiently.

Negative input number

How to Handle:

Convert the input number to its absolute value, as bit positions are the same for positive and negative representations of the same magnitude.

Input is zero

How to Handle:

Return [0,0] since zero has no set bits.

Large input number close to the maximum integer value

How to Handle:

Ensure the solution correctly handles all bits without integer overflow issues; use bitwise operations carefully.

Input is a power of 2

How to Handle:

The solution should correctly identify one odd bit and zero even bits.

Input is a number with alternating 0s and 1s in its binary representation

How to Handle:

The solution must accurately count the number of even and odd bits when there is a mix of both.

Integer overflow when calculating number of bits

How to Handle:

Use bitwise operations and avoid arithmetic operations that could lead to overflow.

All bits are 1

How to Handle:

The solution needs to count all even and odd positions correctly.

Integer with many trailing zeros

How to Handle:

The bitwise and shifting operations are efficient at skipping over trailing zeros, thus handling this case efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type and range of the input number n? Can n be negative?
How many bits are considered for determining even and odd positions? Is it limited by the integer size of the input, or is there an upper bound?
If the binary representation of 'n' has fewer bits than the positions we are considering (e.g., fewer than 2 bits), how should I handle the missing bits? Should I treat them as 0?
Are we guaranteed that 'n' is a valid integer, or do I need to handle potential invalid input or null/empty cases?
What is the expected return type? Should I return a list/array of two integers, or some other data structure to represent the count of even and odd bits?

Brute Force Solution

Approach

The problem requires us to examine the individual bits of a given number. A brute force approach involves inspecting each bit one by one to determine if it's even, odd, and whether it is a 0 or a 1.

Here's how the algorithm would work step-by-step:

Start with the rightmost bit of the number.
Check if this bit is a 0 or a 1.
Determine if this bit is at an even or odd position, starting from the right and counting from zero.
Keep track of the counts of even-positioned bits that are 1 and odd-positioned bits that are 1.
Move to the next bit to the left and repeat steps 2-4.
Continue this process until you have checked all bits of the number.
Finally, you will have the counts of even bits and odd bits that are set to 1.

Code Implementation

def count_even_odd_bits(number):
    even_bits_count = 0
    odd_bits_count = 0
    bit_position = 0

    # Iterate through bits until the number becomes zero
    while number > 0:
        # Check if the current bit is set (equal to 1)
        if number % 2 == 1:

            # Increment even/odd counts based on bit position
            if bit_position % 2 == 0:
                even_bits_count += 1

            else:
                odd_bits_count += 1

        # Shift the number to the right by one bit
        number = number // 2

        # Update the current bit position
        bit_position += 1

    return [even_bits_count, odd_bits_count]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of the number as a series of bits lined up from right to left, starting with the rightmost bit as position 1.
Go through each bit from right to left.
Check the position of the bit. If the position is odd, and the bit is 'on' (equal to 1), count it as an odd bit.
If the position is even, and the bit is 'on' (equal to 1), count it as an even bit.
Keep track of the counts for even and odd bits as you go.
After checking all bits, you will have the total number of even and odd bits that are 'on'.

Code Implementation

def number_of_even_and_odd_bits(number):
    even_bit_count = 0
    odd_bit_count = 0
    bit_position = 1

    # Iterate through the bits of the number
    while number > 0:

        # Check if the current bit is set (equal to 1)
        if number & 1:

            # Increment counters based on bit position
            if bit_position % 2 == 0:
                #Even position
                even_bit_count += 1

            else:
                #Odd position
                odd_bit_count += 1

        # Move to the next bit by right-shifting
        number >>= 1

        # Update position counter
        bit_position += 1

    return [even_bit_count, odd_bit_count]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Negative input number	Convert the input number to its absolute value, as bit positions are the same for positive and negative representations of the same magnitude.
Input is zero	Return [0,0] since zero has no set bits.
Large input number close to the maximum integer value	Ensure the solution correctly handles all bits without integer overflow issues; use bitwise operations carefully.
Input is a power of 2	The solution should correctly identify one odd bit and zero even bits.
Input is a number with alternating 0s and 1s in its binary representation	The solution must accurately count the number of even and odd bits when there is a mix of both.
Integer overflow when calculating number of bits	Use bitwise operations and avoid arithmetic operations that could lead to overflow.
All bits are 1	The solution needs to count all even and odd positions correctly.
Integer with many trailing zeros	The bitwise and shifting operations are efficient at skipping over trailing zeros, thus handling this case efficiently.

Negative input number

How to Handle:

Convert the input number to its absolute value, as bit positions are the same for positive and negative representations of the same magnitude.

Input is zero

How to Handle:

Return [0,0] since zero has no set bits.

Large input number close to the maximum integer value

How to Handle:

Ensure the solution correctly handles all bits without integer overflow issues; use bitwise operations carefully.

Input is a power of 2

How to Handle:

The solution should correctly identify one odd bit and zero even bits.

Input is a number with alternating 0s and 1s in its binary representation

How to Handle:

The solution must accurately count the number of even and odd bits when there is a mix of both.

Integer overflow when calculating number of bits

How to Handle:

Use bitwise operations and avoid arithmetic operations that could lead to overflow.

All bits are 1

How to Handle:

The solution needs to count all even and odd positions correctly.

Integer with many trailing zeros

How to Handle:

The bitwise and shifting operations are efficient at skipping over trailing zeros, thus handling this case efficiently.