Number of Even and Odd Bits

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Number of Even and Odd Bits. Click on different approaches to view the approach and algorithm in detail.

Iterative Bitwise Operations

This method avoids string conversion by using bitwise operations. It repeatedly checks the least significant bit (LSB) of the number n. If the LSB is 1, it increments the appropriate counter (even or odd) based on the current bit position. The number is then right-shifted to process the next bit, and the process continues until the number becomes zero.

Algorithm

Initialize even = 0, odd = 0, and a bit index counter index = 0.\n2. Start a loop that continues as long as n > 0.\n3. Inside the loop, check if the least significant bit is 1 using the bitwise AND operation: (n & 1) == 1.\n4. If the LSB is 1:\n - If the current index is even, increment even.\n - Otherwise, increment odd.\n5. Right-shift n by one position (n >>= 1) to process the next bit.\n6. Increment the index counter.\n7. After the loop terminates, return the array [even, odd].

This method uses bitwise operations to check each bit of the integer without converting it to a string. This is generally more efficient.\n\nThe algorithm proceeds as follows:\n- We loop as long as n is not zero.\n- In each iteration, we check the last bit of n using n & 1.\n- If it's 1, we check the current bit index's parity and update even or odd.\n- We then right-shift n by one (n >>= 1) to discard the last bit and move to the next one.\n- We increment the bit index.\n\njava\nclass Solution {\n public int[] evenOddBit(int n) {\n int even = 0;\n int odd = 0;\n int index = 0;\n while (n > 0) {\n if ((n & 1) == 1) { // Check if the last bit is 1\n if (index % 2 == 0) {\n even++;\n } else {\n odd++;\n }\n }\n n >>= 1; // Right shift to process the next bit\n index++;\n }\n return new int[]{even, odd};\n }\n}\n

Complexity Analysis

Time Complexity: O(log n), as the loop runs once for each bit in the number `n`. The number of bits is proportional to log n.Space Complexity: O(1), as it only uses a few variables to store the counts and the index, regardless of the size of n.

Pros and Cons

Pros:

More efficient than the string approach in both time and space.
Works directly with the integer's binary representation.
Constant space complexity.

Cons:

May be slightly less intuitive for developers not comfortable with bitwise operations.

Code Solutions

Checking out 3 solutions in different languages for Number of Even and Odd Bits. Click on different languages to view the code.

class Solution {
public
  int[] evenOddBit(int n) {
    int[] ans = new int[2];
    for (int i = 0; n > 0; n >>= 1, i ^= 1) {
      ans[i] += n & 1;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Number of Even and Odd Bits

Patterns:

Bit Manipulation