#1356

Easy

LeetCode Problem Workspace

Sort Integers by The Number of 1 Bits

Sort an array of integers by the number of 1's in their binary representation and then by their value in case of ties.

Problem Statement

You are given an integer array arr. The task is to sort the integers in ascending order by the number of 1's in their binary representation. In case two or more integers have the same number of 1 bits, they should be sorted by their value in ascending order.

Return the array after sorting it according to the specified rules. For example, integers with fewer 1 bits come first, and in case of ties, smaller numbers should precede larger ones.

Examples

Example 1

Input: arr = [0,1,2,3,4,5,6,7,8]

Output: [0,1,2,4,8,3,5,6,7] Explantion: [0] is the only integer with 0 bits. [1,2,4,8] all have 1 bit. [3,5,6] have 2 bits. [7] has 3 bits. The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example details omitted.

Example 2

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]

Output: [1,2,4,8,16,32,64,128,256,512,1024] Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Example details omitted.

Constraints

1 <= arr.length <= 500
0 <= arr[i] <= 104

Solution Approach

Bit Counting with a Sorting Function

To solve this problem, start by counting the number of 1 bits in the binary representation of each integer. This can be efficiently done using bitwise operations. After counting the bits, use a custom sorting function that sorts primarily by the number of 1 bits and secondarily by the integer value.

Using Python's Sort with a Key Function

In Python, the built-in sort function can be leveraged by providing a key function. This key function will return a tuple with the bit count and the integer value, ensuring that sorting respects both the number of bits and the value of the integers.

Optimized Sorting

While sorting the entire array can be done with a time complexity of O(n log n), ensuring that the bit counting step is efficient is crucial for maintaining an optimal solution. Using bitwise operations ensures the bit counting step runs in constant time per number.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log{}n)
Space	O(\log n)

The time complexity of the solution is O(n log n) due to the sorting step. The space complexity is O(log n) because of the space required for storing bit counts. The bit counting operation itself runs in O(1) per integer because it is based on the binary representation of the number, which is bounded by a constant size (up to 17 bits for numbers up to 104).

What Interviewers Usually Probe

Check if the candidate understands the efficient use of bitwise operations for counting 1 bits.
Evaluate how well the candidate handles sorting with a custom key function.
Assess whether the candidate can explain the time and space complexities of their approach.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle tie cases where two numbers have the same number of 1 bits.
Using inefficient bit-counting methods that result in slower performance for larger arrays.
Not understanding how to leverage Python’s sorting key function, leading to unnecessary complexity.

Follow-up variants

Modify the problem to sort by the number of 0 bits instead of 1 bits.
Extend the problem to work with negative integers and their binary representations.
Change the sorting order, sorting by the number of 1 bits in descending order.

FAQ

How do I approach sorting by the number of 1 bits in the binary representation?

Start by counting the number of 1 bits in each number using bitwise operations. Then, sort the numbers using these counts, with ties broken by value.

What is the most efficient way to count the number of 1 bits?

The most efficient way is to use the built-in bitwise operations like n & (n - 1) to count bits, which operates in constant time per number.

How does the time complexity of sorting affect the solution?

Sorting dominates the time complexity, resulting in O(n log n). The bit counting step is O(1) per number, so it doesn't impact the overall complexity significantly.

What if two integers have the same number of 1 bits?

If two integers have the same number of 1 bits, they are sorted by their value in ascending order.

Can this approach be applied to other problems involving sorting based on bit manipulation?

Yes, the approach can be generalized to any problem where sorting is based on a custom condition, such as the number of bits set to 1 or other bit-level properties.

terminal

Solution

Solution 1: Custom Sorting

We sort the array $arr$ according to the requirements of the problem, that is, sort in ascending order according to the number of $1$s in the binary representation. If there are multiple numbers with the same number of $1$s in the binary representation, they must be sorted in ascending order by numerical value.

1

2

3

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x: (x.bit_count(), x))

Continue Practicing

#1366 rank teams by votes #1481 least number of unique integers after k removals #1090 largest values from labels