Abstract / Summary

Count how many numbers in a list have even and odd numbers of set bits in their binary representation.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (100k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method evenOddBit. The method receives an integer n and returns a two-element list. The first element counts the number of set bits that occupy even positions in the binary representation of n; the second element counts the set bits that occupy odd positions. The solution relies on bitwise masking combined with the built-in bit_count method to achieve the result in a compact form.

Core Logic

The essential operation is the expression

(n & 0b0101010101).bit_count()

which isolates bits at even indices (starting from the least-significant bit as index 0) by applying a mask that has a 1 in every even position and a 0 elsewhere. The mask 0b0101010101 corresponds to the binary pattern 0101010101, covering the lower ten bits of the integer. After the mask is applied with the bitwise AND operator, the resulting integer contains only the bits from the original number that were in even positions. The call to bit_count() then returns the number of 1s among those isolated bits.

A symmetric operation

(n & 0b1010101010).bit_count()

targets the odd positions. The mask 0b1010101010 has a 1 in each odd position and a 0 in each even position, thereby extracting the odd-indexed bits before counting them.

Both results are collected into a list and returned directly:

return [ (n & 0b0101010101).bit_count(),
         (n & 0b1010101010).bit_count() ]

Edge Cases Handled

The method works correctly for any non-negative integer that fits within the range of Python’s arbitrary-precision integers. When n is zero, both masks produce zero after the AND operation, and bit_count() returns zero for each, yielding [0, 0]. For values of n that have bits set beyond the tenth position, the masks simply ignore those higher bits because the mask literals only cover the lower ten bits. Consequently, the method effectively treats any higher bits as irrelevant to the even-odd count, which aligns with the typical problem constraints that limit the input to ten-bit numbers.

If n is a negative integer, Python represents it using an infinite two’s-complement extension. The bitwise AND with the positive masks will still isolate the lower ten bits of the two’s-complement representation, and bit_count() will count the set bits in that region. This behavior ensures that the method returns a deterministic result even for negative inputs, though the original problem statement usually restricts n to non-negative values.

Performance Optimizations

The implementation achieves high efficiency by avoiding explicit loops or per-bit iteration. The use of constant-size masks means the bitwise AND operation executes in constant time regardless of the magnitude of n. The built-in bit_count method is implemented in C within the Python runtime and operates directly on the binary representation, providing a fast population count without manual bit shifting. By combining masking and bit_count in a single expression, the code minimizes the number of intermediate objects and function calls, leading to reduced overhead.

Because the masks are literals, they are compiled once and reused for every call, eliminating any runtime construction cost. The return statement constructs a list of two integers in a single step, avoiding additional temporary containers. Overall, the approach leverages low-level bitwise operations and native CPU instructions for counting bits, delivering a solution that runs in optimal time for the given task.

Imagine a long row of little light switches that represent a secret code for a number. Some switches are in the even spots and some are in the odd spots. This code takes a number and looks at all those switches at once. It uses special glasses to see only the even switches and counts how many are turned on. Then, it uses different glasses to see only the odd switches and counts those too. It puts these two totals together in a box so the right answers are ready to be used.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python		Java	C++			TS
	WalkCCC	Python		Java	C++
	leetcode.ca	Python		Java	C++	Go	Rust	TS
	Progiez	Python		Java	C++
github	charles-wangkai			Java
	fsq				C++
	JoshCrozier		JS
	lkwq007	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality