Sort Integers by The Number of 1 Bits

Difficulty: Easy | Acceptance: 82.30% | Paid: No Topics: Array, Bit Manipulation, Sorting, Counting

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

• Examples
• Constraints
• Approach 1: Built-in Sort with Custom Comparator
• Approach 2: Brian Kernighan’s Algorithm
• Approach 3: Precomputed Bit Counts (Dynamic Programming)

Examples

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explanation:
[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]

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]
Explanation:
All integers have 1 bit in the binary representation, so you just sort them in ascending order.

Constraints

1 <= arr.length <= 500
0 <= arr[i] <= 10^4

Approach 1: Built-in Sort with Custom Comparator

Intuition Leverage the language’s built-in sorting algorithm but provide a custom key or comparator that sorts primarily by the count of set bits (1s) and secondarily by the integer value itself.

Steps

• Define a helper function or use a built-in method to count the number of 1 bits in an integer.
• Sort the array using a comparator that compares the bit counts first. If bit counts are equal, compare the integer values directly.
• Return the sorted array.

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

Complexity

• Time: O(n log n * k), where n is the number of elements and k is the average number of bits (usually 32 or 64). The sorting dominates the complexity.
• Space: O(n) or O(log n) depending on the sorting algorithm’s space complexity.
• Notes: This is the most concise solution and relies on highly optimized standard library functions.

Approach 2: Brian Kernighan’s Algorithm

Intuition Instead of converting to a string or using built-ins, we manually count the set bits using Brian Kernighan’s algorithm, which repeatedly clears the least significant set bit until the number becomes zero.

Steps

• Implement a helper function countBits(x) that initializes a counter to 0.
• While x is not zero, perform x = x & (x - 1) to clear the least significant set bit, and increment the counter.
• Use this helper function within the sorting logic to determine the primary sort key.

class Solution:
    def sortByBits(self, arr: list[int]) -> list[int]:
        def count_bits(x: int) -> int:
            count = 0
            while x:
                x &= x - 1
                count += 1
            return count
        return sorted(arr, key=lambda x: (count_bits(x), x))

Complexity

• Time: O(n log n * k), where k is the number of set bits in the numbers. This is often faster than checking every bit.
• Space: O(1) auxiliary space (excluding sort space).
• Notes: This approach is efficient for sparse numbers (numbers with few 1 bits).

Approach 3: Precomputed Bit Counts (Dynamic Programming)

Intuition Since the constraints limit the values to 10⁴, we can precompute the number of 1 bits for every number from 0 to the maximum value in the array. This allows O(1) lookup during the sort phase.

Steps

• Find the maximum value in the input array.
• Create an array bits of size max_val + 1.
• Iterate from 1 to max_val to populate bits. Use the relation bits[i] = bits[i >> 1] + (i & 1) to compute counts efficiently using previously computed values.
• Sort the original array using the precomputed bits array as the key.

class Solution:
    def sortByBits(self, arr: list[int]) -> list[int]:
        if not arr:
            return []
        max_val = max(arr)
        bits = [0] * (max_val + 1)
        for i in range(1, max_val + 1):
            bits[i] = bits[i >> 1] + (i & 1)
        return sorted(arr, key=lambda x: (bits[x], x))

Complexity

• Time: O(n + M log n), where M is the maximum value in the array (10⁴). Precomputation takes O(M), and sorting takes O(n log n).
• Space: O(M) to store the precomputed bit counts.
• Notes: This is optimal if the range of numbers is small, as it reduces the bit counting cost during sorting to a simple array lookup.