algoadvance

You are given a positive integer n. You need to return an array answer of size 2 where answer[0] is the number of even-indexed bits set to 1 in the binary representation of n (index starts from 0), and answer[1] is the number of odd-indexed bits set to 1 in the binary representation of n.

Clarifying Questions

  1. Input Constraints: Are there any specific constraints on the value of n?
    • Assume 1 <= n <= 10^9.
  2. Bit Indexing: Should the indexing start from the least significant bit (rightmost bit)?
    • Yes, indexing starts from the least significant bit (rightmost bit at index 0).

Strategy

  1. Binary Representation and Indexing: Convert the integer n to its binary representation. Traverse through each bit while keeping track of the indices to determine whether the bit is at an even or odd index.

  2. Counting the 1’s: As we traverse through the binary string, increment the corresponding counter when a bit set to 1 is found at either an even or odd index.

  3. Return Results: Return the results in an array where the first element is the count of bits set to 1 at even indices, and the second element is the count of bits set to 1 at odd indices.

Code Implementation

def count_even_odd_bits(n: int) -> [int, int]:
    # Initialize counters for even-indexed and odd-indexed bits
    even_count = 0
    odd_count = 0

    # Convert n to its binary representation
    binary_n = bin(n)[2:]  # Remove the '0b' prefix
    
    # Traverse the binary string
    for idx, bit in enumerate(reversed(binary_n)):
        if bit == '1':
            if idx % 2 == 0:
                even_count += 1
            else:
                odd_count += 1
                
    return [even_count, odd_count]

# Example usage:
print(count_even_odd_bits(10))  # Output should be [2, 0] since binary 10 is '1010'

Time Complexity

The time complexity of this solution is O(log n), which corresponds to the number of bits in the binary representation of n. Given that n can be up to (10^9), the number of bits is at most 30 (since (2^{30}) is slightly above (10^9)). This makes the solution efficient.

Try our interview co-pilot at AlgoAdvance.com