Sort array according to count of set bits

Problem Statement

Given an array of non-negative integers, sort the array in decreasing order of count of set bits (1s in binary representation). If two numbers have the same count of set bits, maintain their relative order (stable sort).

Constraints:

• All elements are non-negative integers
• Maintain relative order for elements with equal set bit count

Example:

• Input: arr = [5, 2, 3, 9, 4, 6, 7, 15, 32]
• Output: [15, 7, 5, 3, 9, 6, 2, 4, 32]
• Explanation:
  • 15 = 1111 (4 set bits)
  • 7 = 111 (3 set bits)
  • 5 = 101, 3 = 11, 9 = 1001, 6 = 110 (2 set bits each)
  • 2 = 10, 4 = 100, 32 = 100000 (1 set bit each)

Approach 1: Brute Force (Custom Sort with Counting)

Intuition

Sort using comparator and compute set-bit count during comparisons.

Algorithm

1. Use stable sort over array
2. During each comparison, compute bitCount(a) and bitCount(b)
3. Place element with higher bit count first
4. If counts are equal, keep original order (stable sort)

import java.util.*;

public class Solution {
    private int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
    
    public void sortBySetBits(Integer[] arr) {
        Arrays.sort(arr, (a, b) -> countSetBits(b) - countSetBits(a));
    }
}

Complexity Analysis

• Time Complexity: O(n log n * b) - b is bits per number (at most 32)
• Space Complexity: O(log n) - Sort recursion stack

Approach 2: Optimal (Bucket by Bit Count)

Intuition

Bit count range is bounded (0 to 32 for int). Group numbers by bit count, then rebuild from 32 to 0.

Algorithm

1. Create 33 buckets (0...32)
2. For each number, compute Integer.bitCount(num) and push into corresponding bucket
3. Rebuild array by reading buckets from 32 down to 0
4. Keep insertion order inside each bucket for stability

import java.util.*;

public class Solution {
    public void sortBySetBits(int[] arr) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 33; i++) {
            buckets.add(new ArrayList<>());
        }
        
        for (int num : arr) {
            int count = Integer.bitCount(num);
            buckets.get(count).add(num);
        }
        
        // Reconstruct array in decreasing order of set bits
        int idx = 0;
        for (int i = 32; i >= 0; i--) {
            for (int num : buckets.get(i)) {
                arr[idx++] = num;
            }
        }
    }
}

Complexity Analysis

• Time Complexity: O(n) - One pass to bucket + one pass to rebuild
• Space Complexity: O(n) - Buckets storage

Key Takeaways

1. Brute force comparator repeatedly recomputes bit counts.
2. Bucket approach is best here because bit count range is fixed.
3. Preserve stability by appending in original order inside each bucket.