We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Even and Odd Bits

Number: 2659

Difficulty: Easy

Paid? No

Companies: Meta

Problem Description

Given a positive integer n, return an array containing two numbers: the count of ones at even indices and the count of ones at odd indices in the binary representation of n. The binary bits are indexed from right to left, starting at index 0.

Key Insights

  • The binary representation must be processed starting from the least significant bit (rightmost bit) since indices are defined from right to left.
  • For each bit, if it equals 1, determine whether its index is even or odd and increment the respective counter.
  • Bit manipulation (using bitwise AND and right-shift operations) provides an efficient way to check each bit without converting the number to a string.

Space and Time Complexity

Time Complexity: O(log n) - The algorithm iterates through each bit of n. Space Complexity: O(1) - Only constant extra space is used for counters and index.

Solution

The solution works by initializing two counters, even and odd, to 0. Starting with index 0 and the given number n, the algorithm checks the least significant bit of n using a bitwise AND with 1. If the result is 1, it increments the even counter if the current index is even, or the odd counter if the index is odd. Then, the algorithm right-shifts n by one (dividing by 2) and increments the index. This process continues until n becomes 0. The result is returned as a two-element array [even, odd].

Code Solutions

# Python solution
def evenOddBit(n: int) -> [int, int]:
    even, odd = 0, 0  # Counters for even and odd indices
    index = 0         # Bit index starting from 0 (LSB)
    while n:
        # Check if the current bit is '1'
        if n & 1:
            if index % 2 == 0:
                even += 1  # Increment even counter if index is even
            else:
                odd += 1   # Increment odd counter if index is odd
        n >>= 1  # Right-shift to move to the next bit
        index += 1
    return [even, odd]

# Example usage:
print(evenOddBit(50))  # Output: [1,2]
← Back to All Questions