Code Logo

Sort Integers by The Number of 1 Bits

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an integer array arr, sort the array in ascending order by the number of 1 bits in the binary representation of each integer. If two integers have the same number of 1 bits, sort them by ascending value.

Count the number of 1 bits (popcount) for each integer. The popcount can be computed using built-in functions like Integer.bitCount in Java or bit_count in Python, or via a manual loop. Then sort with a custom comparator: compare popcount first, then value for ties.

Time is O(n log n) for sorting plus O(n) for counting bits. Space is O(1).

Edge cases include an empty array, single element, all zero values (bit count 0), and large numbers with many bits.

The popcount operation counts 1 bits in binary representation. Combined with custom sorting, this reveals patterns about how numbers relate to powers of two and demonstrates secondary sorting when primary keys are equal. The bit count sorting problem demonstrates how binary representation properties can be used as sort keys. The custom comparator first compares bit counts, with value comparison as a secondary tiebreaker to ensure a deterministic ordering. The popcount comparison uses the built-in bit counting function available in most modern programming languages, often mapping to a single CPU instruction for efficiency.

Example Input & Output

Example 1
Input
[7,8,3,5]
Output
[8,3,5,7]
Explanation

8(1bit),3(2),5(2),7(3). Tie: 3<5.

Example 2
Input
[1024,512,256,128,64,32,16,8,4,2,1]
Output
[1,2,4,8,16,32,64,128,256,512,1024]
Explanation

All have 1 bit, sort by value.

Example 3
Input
[]
Output
[]
Explanation

Empty.

Example 4
Input
[0,1,2,3,4,5,6,7,8]
Output
[0,1,2,4,8,3,5,6,7]
Explanation

Bit count order: 0(0),1(1),2(1),4(1),8(1),3(2),5(2),6(2),7(3).

Example 5
Input
[2,3,1]
Output
[1,2,3]
Explanation

1(1bit), 2(1bit), 3(2bits). Tie: 1<2.

Algorithm Flow

Recommendation Algorithm Flow for Sort Integers by The Number of 1 Bits
Recommendation Algorithm Flow for Sort Integers by The Number of 1 Bits

Solution Approach

For each element, compute its bit count. Sort by bit count ascending, then by value ascending for ties.

function solution(arr) {
  function bitCount(n) {
    var count = 0;
    while (n) { count += n & 1; n >>>= 1; }
    return count;
  }
  arr.sort(function(a, b) {
    var ca = bitCount(a), cb = bitCount(b);
    if (ca !== cb) return ca - cb;
    return a - b;
  });
  return arr;
}

Time O(n log n), Space O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] arr) {
        Integer[] boxed=Arrays.stream(arr).boxed().toArray(Integer[]::new);
        Arrays.sort(boxed,(a,b)->{
            int ca=Integer.bitCount(a),cb=Integer.bitCount(b);
            if(ca!=cb)return ca-cb;
            return a-b;
        });
        return Arrays.stream(boxed).mapToInt(i->i).toArray();
    }
}