# Sort Integers by The Number of 1 Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits)
Canonical: https://scaleengineer.com/dsa/problems/sort-integers-by-the-number-of-1-bits
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Mapbox](https://scaleengineer.com/companies/mapbox)
---
## Problem
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`

# Approaches
## Custom Sort with Manual Bit Counting
This approach involves using the standard library's sorting function but providing a custom comparison logic. The comparison logic first calculates the number of set bits (1s) for each of the two numbers being compared and then uses these counts as the primary sorting key. The numbers themselves are used as the secondary sorting key for tie-breaking.
**Time:** O(N * K * log N), where `N` is the number of elements in the array and `K` is the number of bits in an integer. The `log N` factor comes from the sort, and for each comparison, we perform a `O(K)` operation to count bits. Since `K` is small (at most 14 for the given constraints), this is feasible but not optimal. · **Space:** O(N) to store the boxed `Integer` array. The sorting algorithm itself might use `O(log N)` (quicksort) or `O(N)` (mergesort/timsort) auxiliary space.
**Pros:** Conceptually straightforward and easy to understand.; Leverages the standard library's powerful and stable sorting capabilities.
**Cons:** Less efficient due to the repeated calculation of bit counts for the same numbers during the sorting process.; Requires converting the primitive `int[]` to an `Integer[]`, which introduces memory and performance overhead due to boxing.
### Explanation
The core of this method is a custom `Comparator`. When the sorting algorithm needs to compare two integers, `a` and `b`, the comparator is invoked. Inside the comparator, we first need a helper function, say `countSetBits(n)`, to count the 1s in the binary representation of an integer. This can be done by repeatedly checking the last bit with `n & 1` and right-shifting the number (`n >>= 1`) until it becomes zero. We call this helper function for both `a` and `b` to get `bitCountA` and `bitCountB`. If `bitCountA` is not equal to `bitCountB`, we sort based on the bit counts. If the bit counts are the same, we sort based on the integer values themselves. Since the input array `arr` contains primitive `int`s, we first need to convert it to an array of `Integer` objects to use a custom `Comparator` with `Arrays.sort()`. After sorting, we convert it back to an `int[]`.

```java
class Solution {
    private int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1); // Brian Kernighan's algorithm
            count++;
        }
        return count;
    }

    public int[] sortByBits(int[] arr) {
        Integer[] boxedArr = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            boxedArr[i] = arr[i];
        }

        Arrays.sort(boxedArr, (a, b) -> {
            int countA = countSetBits(a);
            int countB = countSetBits(b);
            if (countA != countB) {
                return countA - countB;
            } else {
                return a - b;
            }
        });

        for (int i = 0; i < arr.length; i++) {
            arr[i] = boxedArr[i];
        }
        return arr;
    }
}
```
### Algorithm
- Create a helper function `countSetBits(int n)` that iteratively counts the set bits. A simple way is to loop, check the last bit with `n & 1`, and right-shift `n` (`n >>= 1`). A more optimized way is using Brian Kernighan's algorithm (`n &= (n - 1)`).
- Convert the input `int[] arr` to an `Integer[]` array to allow for sorting with a custom comparator.
- Use `Arrays.sort()` on the `Integer[]` array, providing a custom `Comparator`.
- The `Comparator`'s `compare(a, b)` method will:
  - a. Calculate `countA = countSetBits(a)`.
  - b. Calculate `countB = countSetBits(b)`.
  - c. If `countA` is different from `countB`, return `countA - countB` to sort by bit count.
  - d. Otherwise, return `a - b` to sort by value as a tie-breaker.
- Copy the sorted `Integer` elements back into the original `int[] arr`.

## Optimized Sort with Built-in Bit Count
This approach is a direct optimization of the previous one. Instead of implementing our own bit counting logic, we leverage the highly optimized, often hardware-accelerated, built-in function provided by the language (e.g., `Integer.bitCount()` in Java). This significantly speeds up the comparison step within the sort.
**Time:** O(N log N). The sorting algorithm dominates the complexity. Each comparison is now effectively `O(1)` because `Integer.bitCount()` is extremely fast. · **Space:** O(N) for the boxed `Integer` array. The sort itself might take additional space (`O(log N)` to `O(N)`).
**Pros:** Much faster than the manual bit counting approach due to the `O(1)` nature of the built-in function.; Clean, readable, and idiomatic code.; Provides an excellent balance of performance and implementation simplicity.
**Cons:** Still involves the overhead of boxing primitives to `Integer` objects and unboxing them back.; Bit counts for the same number might be re-calculated multiple times during the sort, although each calculation is very fast.
### Explanation
The overall structure is identical to the first approach: convert the array to `Integer[]`, sort with a custom `Comparator`, and convert back. The key difference lies in the `Comparator`. Instead of calling a custom helper function to count bits, we call `Integer.bitCount(n)`. This function is typically implemented using very fast machine-level instructions (like `POPCNT`) and can be considered an `O(1)` operation for a fixed-size integer. The comparison logic remains the same: get bit counts for `a` and `b`, if they differ, return their difference; otherwise, return the difference of `a` and `b`.

```java
import java.util.Arrays;

class Solution {
    public int[] sortByBits(int[] arr) {
        Integer[] boxedArr = new Integer[arr.length];
        for (int i = 0; i < arr.length; i++) {
            boxedArr[i] = arr[i];
        }

        // Use a lambda expression for the custom comparator
        Arrays.sort(boxedArr, (a, b) -> {
            int countA = Integer.bitCount(a);
            int countB = Integer.bitCount(b);
            if (countA != countB) {
                return countA - countB;
            } else {
                return a - b;
            }
        });

        for (int i = 0; i < arr.length; i++) {
            arr[i] = boxedArr[i];
        }
        return arr;
    }
}
```
### Algorithm
- Convert the input `int[] arr` to an `Integer[]` array.
- Use `Arrays.sort()` on the `Integer[]` array with a custom `Comparator`.
- The `Comparator`'s `compare(a, b)` method will:
  - a. Calculate `countA = Integer.bitCount(a)`.
  - b. Calculate `countB = Integer.bitCount(b)`.
  - c. If `countA != countB`, return `countA - countB`.
  - d. Else, return `a - b`.
- Copy the sorted `Integer` elements back into the original `int[] arr`.

## Pre-computation using Encoding
This is a highly efficient approach that avoids both custom comparators and repeated computations. The idea is to 'decorate' each number in the array by encoding its primary and secondary sorting keys into a single new number. After sorting these new numbers using a standard integer sort, we 'undecorate' them to get the final sorted result.
**Time:** O(N log N). The encoding step is `O(N)`, the sorting step is `O(N log N)`, and the decoding step is `O(N)`. The sorting step is the bottleneck. · **Space:** O(log N) or O(1). This approach can be done in-place. The space used is only the auxiliary space required by the sorting algorithm itself (e.g., `Arrays.sort` for primitives in Java uses a dual-pivot quicksort, which has an average space complexity of `O(log N)`).
**Pros:** Very efficient; bit counts are calculated only once per element.; Avoids the overhead of custom comparators and boxing/unboxing.; Excellent space complexity as it can be done in-place on the input array.
**Cons:** The encoding logic might seem a bit 'magical' or less intuitive at first glance.; Requires careful selection of the multiplier `M` based on the problem constraints to avoid overflow and ensure correctness.
### Explanation
The sorting criteria are (1) number of bits, and (2) the value itself. We can combine these into a single integer for sorting. We can create a new value for each number `x` using the formula: `encoded_value = (bit_count * M) + x`. Here, `M` must be a number larger than any possible value of `x`. Since the constraint is `0 <= arr[i] <= 10^4`, we can choose `M = 10001`. By using this formula, if two numbers have different bit counts, the `bit_count * M` term will dominate, ensuring they are sorted correctly. If they have the same bit count, the `x` term will act as the tie-breaker. This allows us to use a standard, fast integer sort without the overhead of a custom comparator.

```java
import java.util.Arrays;

class Solution {
    public int[] sortByBits(int[] arr) {
        // The constraint is arr[i] <= 10000. We can use 10001 as a multiplier.
        // Max bit count for 10000 is 14.
        // Max encoded value will be around 14 * 10001 + 10000, which fits in an int.
        for (int i = 0; i < arr.length; i++) {
            arr[i] += Integer.bitCount(arr[i]) * 10001;
        }

        Arrays.sort(arr);

        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] % 10001;
        }

        return arr;
    }
}
```
### Algorithm
- Define a constant `M` (e.g., 10001) that is larger than the maximum possible element value in `arr`.
- **Encode:** Iterate through the array `arr`. For each element `arr[i]`, update it in-place to `Integer.bitCount(arr[i]) * M + arr[i]`.
- **Sort:** Sort the modified `arr` using a standard library sort function (e.g., `Arrays.sort(arr)`).
- **Decode:** Iterate through the now-sorted `arr`. For each element `arr[i]`, update it to `arr[i] % M` to retrieve the original number.
- Return the modified `arr`.

# Solutions
### Java

```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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]: return sorted(
        arr, key=lambda x: (x . bit_count(), x))

```