{x}
blog image

Sort Integers by The Number of 1 Bits

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 array after sorting it.

 

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 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.

 

Constraints:

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

1356. Sort Integers by The Number of 1 Bits

Problem Description

Given an integer array arr, sort the integers in ascending order by the number of 1s in their binary representation. If two or more integers have the same number of 1s, sort them in ascending order.

Solutions

This problem can be solved efficiently using custom sorting functions. The core idea is to create a comparator (or a key function in languages like Python) that determines the order based on the number of 1s in the binary representation and then the numerical value itself as a tie-breaker.

Solution 1: Custom Sorting with Arithmetic Trick (In-place)

This approach modifies the array directly using an arithmetic trick to embed the bit count into the number, enabling a single sort operation. After sorting, the bit count is extracted.

Time Complexity: O(n log n) due to the sorting operation. The other operations are linear. Space Complexity: O(1) (in-place sorting).

Code:

Python:

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        for i in range(len(arr)):
            arr[i] += bin(arr[i]).count('1') * 100000  # Add bit count * large constant to each element
        arr.sort()
        for i in range(len(arr)):
            arr[i] %= 100000  #Remove bit count
        return arr

Java:

class Solution {
    public int[] sortByBits(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            arr[i] += Integer.bitCount(arr[i]) * 100000;
        }
        Arrays.sort(arr);
        for (int i = 0; i < n; ++i) {
            arr[i] %= 100000;
        }
        return arr;
    }
}

C++:

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        for (int& v : arr) {
            v += __builtin_popcount(v) * 100000;
        }
        sort(arr.begin(), arr.end());
        for (int& v : arr) {
            v %= 100000;
        }
        return arr;
    }
};

Go:

func sortByBits(arr []int) []int {
	for i, v := range arr {
		arr[i] += bits.OnesCount(uint(v)) * 100000
	}
	sort.Ints(arr)
	for i := range arr {
		arr[i] %= 100000
	}
	return arr
}

Note: The constant 100000 is chosen to be large enough to avoid collisions when adding the bit count. You might need to adjust it depending on the input range.

Solution 2: Custom Comparator/Key Function (More Readable)

This approach uses a custom comparator (or key function) to directly compare elements based on the number of 1s and then the numerical value. This is often more readable and avoids the potential for collisions in Solution 1.

Time Complexity: O(n log n), dominated by the sorting algorithm. Space Complexity: O(n) in the worst case (for creating a copy in some implementations), O(log n) on average for the recursive calls of the sorting algorithm.

Code:

Python:

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

Java:

class Solution {
    public int[] sortByBits(int[] arr) {
        Integer[] t = Arrays.stream(arr).boxed().toArray(Integer[]::new); // Convert to Integer array
        Arrays.sort(t, (a, b) -> {
            int countA = Integer.bitCount(a);
            int countB = Integer.bitCount(b);
            return Integer.compare(countA, countB) != 0 ? Integer.compare(countA, countB) : Integer.compare(a, b);
        });
        return Arrays.stream(t).mapToInt(Integer::intValue).toArray(); // Convert back to int array
    }
}

C++:

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [&](int a, int b) {
            int countA = __builtin_popcount(a);
            int countB = __builtin_popcount(b);
            return countA != countB ? countA < countB : a < b;
        });
        return arr;
    }
};

Go:

func sortByBits(arr []int) []int {
	sort.Slice(arr, func(i, j int) bool {
		countI := bits.OnesCount(uint(arr[i]))
		countJ := bits.OnesCount(uint(arr[j]))
		if countI != countJ {
			return countI < countJ
		}
		return arr[i] < arr[j]
	})
	return arr
}

Both solutions achieve the same result. Solution 2 is generally preferred for its readability and lack of reliance on potentially problematic magic numbers. Choose the solution that best suits your coding style and language preferences.