Sort Integers by The Number of 1 Bits: Custom Sort with Bit Counting

LeetCode Sort Integers by The Number of 1 Bits (Problem 1356) asks you to sort an array of integers in ascending order by the number of 1 bits in their binary representation. If two numbers have the same number of 1 bits, sort them by their value in ascending order.

For example, given [0, 1, 2, 3, 4, 5, 6, 7, 8], the sorted result is [0, 1, 2, 4, 8, 3, 5, 6, 7]. The number 0 has zero 1 bits, so it comes first. Then 1, 2, 4, and 8 each have exactly one 1 bit, sorted by value. Next come 3, 5, and 6 with two 1 bits. Finally 7, which has three 1 bits, goes last.

The approach: custom sort key

The idea is simple. Python's sorted() function accepts a key argument that tells it how to compare elements. You want to sort primarily by the number of 1 bits, and secondarily by the value itself. A tuple (bit_count, value) does exactly that.

Python compares tuples element by element. Two numbers with different bit counts get sorted by bit count. Two numbers with the same bit count fall through to the second element of the tuple, which is the value. This gives you both the primary and tiebreaker sort in one clean expression.

To count the 1 bits, you can convert the number to a binary string with bin(x) and count the '1' characters.

Python solution

def sort_by_bits(arr: list[int]) -> list[int]:
    return sorted(arr, key=lambda x: (bin(x).count('1'), x))

That is the entire solution. One line of actual logic.

Alternative: using bit_count()

Python 3.10 introduced int.bit_count(), which returns the number of 1 bits directly without string conversion. If you are using Python 3.10 or later, this is cleaner and slightly faster.

def sort_by_bits(arr: list[int]) -> list[int]:
    return sorted(arr, key=lambda x: (x.bit_count(), x))

Both approaches produce the same result. The bit_count() version avoids creating a temporary string for each number, so it is more efficient in practice. In an interview, either version is perfectly fine.

How tuple comparison works

When you pass key=lambda x: (bin(x).count('1'), x) to sorted(), Python builds a tuple for each element and compares tuples lexicographically.

For numbers 3 and 5:

• 3 has binary 11, so its key is (2, 3)
• 5 has binary 101, so its key is (2, 5)
• Both have 2 bits set, so Python compares the second element: 3 comes before 5

For numbers 1 and 3:

• 1 has binary 1, so its key is (1, 1)
• 3 has binary 11, so its key is (2, 3)
• 1 has fewer bits set, so 1 comes first regardless of value

This tuple trick works for any multi-criteria sort. You will see it again and again in sorting problems.

Walkthrough: sorting [0, 1, 2, 3, 4, 5, 6, 7, 8]

Let's trace through the algorithm step by step. The goal is to group numbers by their bit count, sort within each group by value, and then concatenate the groups.

The key insight is that Python's sorted() with a tuple key handles both the grouping and the tiebreaking in a single pass. You do not need to manually group the numbers first. The sort algorithm takes care of everything.

Complexity analysis

The time complexity is dominated by the sort, which is O(n log n). Counting bits for each number is O(log m) where m is the maximum value, but since the problem constrains values to 0 to 10^4, this is effectively constant. The space complexity is O(n) for the sorted output.

Building blocks

This problem combines two reusable building blocks that CodeBricks drills independently:

Counting set bits

The ability to count how many bits are set to 1 in an integer. This is a fundamental bit manipulation operation that appears in many problems.

count = bin(x).count('1')

count = x.bit_count()

count = 0
while x:
    x &= x - 1
    count += 1

Custom sort keys

Using Python's key parameter with a tuple to define multi-criteria sorting. The first element of the tuple is the primary sort criterion, the second is the tiebreaker. This pattern generalizes to any number of criteria.

sorted(arr, key=lambda x: (primary(x), secondary(x)))

Once you can fluently apply bit counting and tuple sort keys, this problem becomes a direct combination. You stop thinking about the mechanics and start recognizing the pattern immediately.

Edge cases

All zeros. If every element is 0, every key is (0, 0). The array stays unchanged since all elements are identical.

All same bit count. If every number has the same number of 1 bits, the sort degenerates to a regular sort by value. The tuple comparison falls through to the second element for every pair.

Powers of two. Numbers like 1, 2, 4, 8, 16 all have exactly one 1 bit. They form a single group and get sorted by value within that group.

Maximum value. The constraint says values go up to 10^4 (10000 in binary is 10011100010000), which has at most 14 bits. Bit counting is fast even at the upper bound.

From understanding to recall

This problem is easy to understand once you see the tuple key trick. But in an interview, you need to produce it quickly without hesitation. Remembering that "sort by bit count with value as tiebreaker" maps to key=lambda x: (bin(x).count('1'), x) requires practice.

Spaced repetition builds that recall. You write the one-liner from scratch today, then again in a few days, then a week later. Each repetition makes the retrieval faster. When you encounter a custom sort problem in the future, the tuple key pattern will surface automatically.

Related posts

• Number of 1 Bits - The foundational bit counting problem. Covers both the right-shift approach and Brian Kernighan's n & (n-1) algorithm that this problem uses as a building block.
• Counting Bits - Extends bit counting to an entire range of numbers using dynamic programming. If you like the bit counting aspect of this problem, Counting Bits takes it further.
• Sort an Array - Builds merge sort from scratch. While this problem uses Python's built-in sort with a custom key, Sort an Array teaches you what happens under the hood of O(n log n) sorting.