Leetcode – Sort Integers by The Number of 1 Bits Solution

Spread the love

The problem “Sort Integers by The Number of 1 Bits” on Leetcode provides a unique blend of bit manipulation and sorting, which is a test of both your algorithmic skills and your understanding of Python’s built-in capabilities. It’s a problem that might look simple at first glance but can actually be approached in various ways, each with its own set of merits and demerits.

In this article, we will delve into the problem’s specifics, the constraints that come with it, multiple approaches to solve it, and the time and space complexities of each solution.

Problem Statement

The problem can be found on Leetcode and is defined as follows:

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1 bits in their binary representation and, in case of two or more integers have the same number of 1 bits you have to sort them in ascending order.

Return the sorted array.

Examples:

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

Input: arr = [10000,10000]
Output: [10000,10000]

Approaches to Solve the Problem

Brute-force Approach

One of the simplest ways to approach this problem is to create a function that counts the number of 1 bits for each number, sort the array based on those counts, and then sort by the number itself if the counts are the same. We can make use of Python’s built-in sorted function and provide a custom key.

Here’s a Python code snippet for the brute-force approach:

def count_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def sortByBits(arr):
    return sorted(arr, key=lambda x: (count_bits(x), x))

Time Complexity: O(n log ⁡n)
Space Complexity: O(1)

Optimized Approach Using Cached Bits

An optimized approach is to pre-calculate and cache the bit counts for all the numbers to reduce redundant calculations. Given the constraint of 0≤arr[i]≤10^4, we can calculate the bit counts for all numbers from 0 to 10^4 in advance and use them for sorting.

Here’s how to do it in Python:

def sortByBits(arr):
    bits_count_cache = {i: bin(i).count('1') for i in range(10**4 + 1)}
    return sorted(arr, key=lambda x: (bits_count_cache[x], x))

Time Complexity: O(n log ⁡n)
Space Complexity: O(1)

Why These Approaches Work

Brute-force Approach

This approach works by explicitly counting the bits for each number in the array and sorting them based on those counts and the number itself. It uses the built-in sorted function in Python, which has a time complexity of O(n log ⁡n).

Optimized Approach Using Cached Bits

The optimized approach speeds up the bit-counting step by using a pre-calculated dictionary. Although the sorting time complexity remains O(n log ⁡n), the bit-counting operations are reduced to O(1), making it slightly faster in practice.

Edge Cases

  1. Duplicate Numbers: The function should be able to handle cases where there are duplicate numbers in the array. The problem statement specifies that duplicates should remain in their original order, which Python’s sorted function handles automatically as it is stable.
  2. Single Element Array: The function should return the array as is, as an array with a single element is already sorted.

Conclusion

The “Sort Integers by The Number of 1 Bits” problem is a fascinating blend of bit manipulation and sorting. It serves as a good practice for understanding how to optimize sorting algorithms with additional constraints.

The brute-force approach is simpler to understand and implement, but the optimized approach shows how pre-calculation and caching can sometimes provide significant performance boosts. Both approaches use Python’s built-in sorted function for sorting, emphasizing the flexibility and power of built-in Python features.

Leave a Reply