Skip to content

1356. Sort Integers by The Number of 1 Bits 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
  }
};

1
2
3
4
5
6
7
8
9
class Solution {
  public int[] sortByBits(int[] arr) {
    return Arrays.stream(arr)
        .boxed()
        .sorted(Comparator.comparingInt(Integer::bitCount).thenComparingInt(a -> a))
        .mapToInt(Integer::intValue)
        .toArray();
  }
}

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