Code Implementation

class Solution:
    def sortByBits(self, arr):
        return sorted(arr, key=lambda x: (bin(x).count('1'), x))
      

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);
            if (countA == countB)
                return a < b;
            return countA < countB;
        });
        return arr;
    }
};
      

class Solution {
    public int[] sortByBits(int[] arr) {
        Integer[] nums = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nums[i] = arr[i];
        }
        Arrays.sort(nums, (a, b) -> {
            int countA = Integer.bitCount(a);
            int countB = Integer.bitCount(b);
            if (countA == countB) return a - b;
            return countA - countB;
        });
        for (int i = 0; i < arr.length; i++) {
            arr[i] = nums[i];
        }
        return arr;
    }
}
      

var sortByBits = function(arr) {
    return arr.sort((a, b) => {
        const countA = a.toString(2).split('1').length - 1;
        const countB = b.toString(2).split('1').length - 1;
        if (countA === countB) return a - b;
        return countA - countB;
    });
};
      

Problem Description

• Each element in arr is a non-negative integer.
• There is only one valid sorted output for any input.
• All elements are used exactly once; do not reuse or omit elements.

Thought Process

Solution Approach

1. Count 1-bits: For every integer in arr, compute the number of 1s in its binary representation. This is often called the Hamming weight or population count. Most languages offer a built-in or easy way to do this (e.g., bin(x).count('1') in Python, __builtin_popcount in C++).
2. Custom Sort: Sort the array using a custom key. The key should be a tuple: first, the bit count; second, the number itself. This ensures that if two numbers have the same bit count, they are sorted by their actual value.
3. Return the Result: After sorting, return the modified array.

• The tuple (bit_count, value) ensures the primary sort is by 1-bits, and the secondary sort is by the integer value.
• This approach is concise, readable, and leverages the language's built-in sorting stability.

• We use built-in functions for counting 1-bits for efficiency and clarity.
• No extra data structures are needed beyond the temporary sort keys.

Example Walkthrough

1. Compute the number of 1-bits for each number:
   • 0: 0b0 → 0
   • 1: 0b1 → 1
   • 2: 0b10 → 1
   • 3: 0b11 → 2
   • 4: 0b100 → 1
   • 5: 0b101 → 2
   • 6: 0b110 → 2
   • 7: 0b111 → 3
   • 8: 0b1000 → 1
2. Group numbers by their 1-bit counts:
   • 0 bits: [0]
   • 1 bit: [1, 2, 4, 8]
   • 2 bits: [3, 5, 6]
   • 3 bits: [7]
3. Sort within each group by value:
   • [0]
   • [1, 2, 4, 8]
   • [3, 5, 6]
   • [7]
4. Concatenate the groups: [0, 1, 2, 4, 8, 3, 5, 6, 7]

Time and Space Complexity

• Counting 1-bits for every number: O(N * B), where N is the number of elements and B is the number of bits in the largest number.
• Sorting: O(N log N)
• Total: O(N * B + N log N)

• If the bit-count operation is fast (constant time with hardware intrinsics), the overall complexity is dominated by sorting: O(N log N).
• Space: O(N) for the sort (depending on implementation; in-place sorts may be O(1) extra).

• Each number's bit count is computed once.
• Sorting with a custom key is efficient and leverages the language's optimized sort algorithms.

Summary