Is Number of Even and Odd Bits easy or hard?

Number of Even and Odd Bits is categorized as an Easy problem. It focuses on basic bit manipulation concepts such as checking set bits and shifting integers. Developers comfortable with binary operations typically solve it in a few lines of code.

Number of Even and Odd Bits Python/Java solution

In Python, repeatedly check n & 1 and shift with n >>= 1 while tracking the bit index. In Java, use the same logic with bitwise operators and integer variables. Both implementations run in O(log n) time and constant space since they process each bit once.

How to solve Number of Even and Odd Bits in O(log n)?

Use a loop that inspects the least significant bit with n & 1 and keeps track of the current bit index. If the bit is 1, increment the even or odd counter based on whether the index is even or odd. Shift the number right using n >>= 1 after each step. Continue until the number becomes zero.

What is the best approach for Number of Even and Odd Bits?

The bit manipulation approach is the most efficient. Iterate through the bits of the integer using n & 1 to check the current bit and right shift the number each step. Track the bit index to separate even and odd positions. This solution runs in O(log n) time and O(1) space.

Is Number of Even and Odd Bits asked at Google/Amazon/Meta?

This problem represents a typical bit manipulation exercise often used in technical interviews and coding assessments. Variations of bit counting and bit position analysis appear in interviews at companies like Google, Amazon, and Meta because they test understanding of binary operations and low-level reasoning.

What data structure is used in Number of Even and Odd Bits?

The problem primarily uses bit manipulation rather than traditional data structures. The algorithm operates directly on the integer’s binary representation using bitwise operations such as AND (&) and right shift (>>). The final result is stored in a simple array of two integers.

What is the time complexity of Number of Even and Odd Bits?

The optimal solution runs in O(log n) time because the algorithm processes each bit of the integer once. Since an integer with value n has roughly log2(n) bits, the loop executes that many iterations. Space complexity remains O(1) when using direct bit manipulation.

Description Hints 2 Solution Video 3:29

2595. Number of Even and Odd Bits

Easy73.4% acceptance1 company

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

Asked at 1 company

Google

Topics

Bit Manipulation

Hints open one at a time

Hint 1

Maintain two integer variables, even and odd, to count the number of even and odd indices in the binary representation of integer n.

Hint 2

Divide n by 2 while n is positive, and if n modulo 2 is 1, add 1 to its corresponding variable.

3:29

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution