Number of Even and Odd Bits

Easy
690.

Number of Even and Odd Bits

Number of Even and Odd Bits is an easy coding problem on math and bit manipulation, asked in TCS, Wipro and Cognizant interviews.

Let even be the number of set bits at even indices of n's binary representation, and odd the number at odd indices. Index 0 is the least significant bit.

Return [even, odd].

Example 1

Input
n = 50
Output
[1,2]
Explanation
50 is 110010 in binary: bit 1 and bit 4 and bit 5 are set, so one even index (4) and two odd ones (1 and 5).

Example 2

Input
n = 2
Output
[0,1]
Explanation
2 is 10 — only bit 1 is set.

Example 3

Input
n = 1
Output
[1,0]

Constraints

  • 1 <= n <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number[]}
 */
var evenOddBit = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Even and Odd Bits — Solution in Python, Java & C++

Number of Even and Odd Bits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Even and Odd Bits is an easy coding problem on math and bit manipulation, asked in TCS, Wipro and Cognizant interviews.

  • Difficulty: Easy
  • Topics: Math, Bit Manipulation
  • Asked at: TCS, Wipro, Cognizant
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Let even be the number of set bits at even indices of n's binary representation, and odd the number at odd indices. Index 0 is the least significant bit.

Return [even, odd].

Example 1

Input: n = 50
Output: [1,2]
Explanation: 50 is 110010 in binary: bit 1 and bit 4 and bit 5 are set, so one even index (4) and two odd ones (1 and 5).

Example 2

Input: n = 2
Output: [0,1]
Explanation: 2 is 10 — only bit 1 is set.

Example 3

Input: n = 1
Output: [1,0]

Constraints

  • 1 <= n <= 1000

Hints for Number of Even and Odd Bits

  1. Hint 1

    Walk the bits from the least significant end, keeping the index.

  2. Hint 2

    v & 1 tests the current bit and v >>= 1 moves to the next.

  3. Hint 3

    The index's parity decides which counter goes up.

How to solve Number of Even and Odd Bits

Shift the number right one bit at a time and keep a position counter; the parity of the position selects the bucket.

Approach

  1. Start i = 0, even = 0, odd = 0.
  2. While n > 0: if the low bit is set, increment even when i is even and odd otherwise.
  3. Shift n right and increment i.

Why it works

Right-shifting by one moves bit i+1 into the low position, so the counter i always names the bit currently being tested.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Counting from the most significant end reverses the index parity and swaps the two answers.
  • Index 0 is even, so the least significant bit belongs to even.

Reference solution

Python

from typing import List

def evenOddBit(n: int) -> List[int]:
    even = odd = 0
    i = 0
    while n > 0:
        if n & 1:
            if i % 2 == 0:
                even += 1
            else:
                odd += 1
        n >>= 1
        i += 1
    return [even, odd]

Java

public static int[] evenOddBit(int n) {
    int even = 0, odd = 0, i = 0;
    while (n > 0) {
        if ((n & 1) == 1) {
            if (i % 2 == 0) even++;
            else odd++;
        }
        n >>= 1;
        i++;
    }
    return new int[] { even, odd };
}

C++

vector<int> evenOddBit(int n) {
    int even = 0, odd = 0, i = 0;
    while (n > 0) {
        if (n & 1) {
            if (i % 2 == 0) even++;
            else odd++;
        }
        n >>= 1;
        i++;
    }
    return { even, odd };
}

JavaScript

var evenOddBit = function(n) {
    var even = 0, odd = 0, i = 0;
    while (n > 0) {
        if ((n & 1) === 1) {
            if (i % 2 === 0) even++;
            else odd++;
        }
        n >>= 1;
        i++;
    }
    return [even, odd];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation