1356. Sort Integers by The Number of 1 Bits

• Time: $O(\texttt{sort})$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  vector<int> sortByBits(vector<int>& arr) {
    ranges::sort(arr, ranges::less{}, [](const int a) {
      const int bitCount = bitset<32>(a).count();
      return pair<int, int>{bitCount, a};
    });
    return arr;
  }
};

class Solution {
  public int[] sortByBits(int[] arr) {
    Integer[] boxedArr = Arrays.stream(arr).boxed().toArray(Integer[] ::new);
    Arrays.sort(boxedArr, Comparator.comparingInt(Integer::bitCount).thenComparingInt(a -> a));
    return Arrays.stream(boxedArr).mapToInt(Integer::intValue).toArray();
  }
}

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