Get started

Number of Even and Odd Bits — Easy Problem & Solution

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.

  • 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

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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue