Sort Integers by The Number of 1 Bits

Easy
371.

Sort Integers by The Number of 1 Bits

Sort Integers by The Number of 1 Bits is an easy coding problem on arrays, sorting and bit manipulation, asked in Amazon and Adobe interviews.

Given an integer array arr, sort it in ascending order by the number of 1 bits in each value's binary representation. Values with the same bit count are sorted by their numeric value, ascending.

Example 1

Input
arr = [0,1,2,3,4,5,6,7,8]
Output
[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]
Explanation
Every value has exactly one set bit.

Example 3

Input
arr = [3,5,6]
Output
[3,5,6]

Constraints

  • 1 <= arr.length <= 40
  • 0 <= arr[i] <= 10000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var sortByBits = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sort Integers by The Number of 1 Bits — Problem & Solution

Sort Integers by The Number of 1 Bits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Sort Integers by The Number of 1 Bits is an easy coding problem on arrays, sorting and bit manipulation, asked in Amazon and Adobe interviews.

Problem statement

Given an integer array arr, sort it in ascending order by the number of 1 bits in each value's binary representation. Values with the same bit count are sorted by their numeric value, ascending.

Example 1

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [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]
Explanation: Every value has exactly one set bit.

Example 3

Input: arr = [3,5,6]
Output: [3,5,6]

Constraints

  • 1 <= arr.length <= 40
  • 0 <= arr[i] <= 10000

Hints for Sort Integers by The Number of 1 Bits

  1. Hint 1

    Count set bits by repeatedly testing the lowest bit and shifting right.

  2. Hint 2

    Sort with a comparator: bit count first, then the value itself.

  3. Hint 3

    x & (x - 1) clears the lowest set bit, giving a loop that runs once per set bit.

How to solve Sort Integers by The Number of 1 Bits

Sort with key (popcount, value).

Approach

  1. Compute each value's set-bit count.
  2. Sort by (bits, value).

Why it works

The composite key implements the two-level order directly.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • x & (x - 1) clears the lowest set bit — a loop that runs once per bit.

Reference solution

Python

def sortByBits(arr):
    return sorted(arr, key=lambda x: (bin(x).count("1"), x))

Java

public static int[] sortByBits(int[] arr) {
    Integer[] boxed = new Integer[arr.length];
    for (int i = 0; i < arr.length; i++) boxed[i] = arr[i];
    Arrays.sort(boxed, (a, b) -> {
        int pa = Integer.bitCount(a), pb = Integer.bitCount(b);
        if (pa != pb) return pa - pb;
        return a - b;
    });
    int[] out = new int[arr.length];
    for (int i = 0; i < arr.length; i++) out[i] = boxed[i];
    return out;
}

C++

vector<int> sortByBits(vector<int>& arr) {
    vector<int> out = arr;
    sort(out.begin(), out.end(), [](int a, int b) {
        int pa = __builtin_popcount((unsigned) a);
        int pb = __builtin_popcount((unsigned) b);
        if (pa != pb) return pa < pb;
        return a < b;
    });
    return out;
}

JavaScript

var sortByBits = function(arr) {
    const popcount = function(x) {
        let count = 0, v = x;
        while (v > 0) {
            count += v & 1;
            v >>>= 1;
        }
        return count;
    };
    return arr.slice().sort(function(a, b) {
        const pa = popcount(a), pb = popcount(b);
        return pa !== pb ? pa - pb : a - b;
    });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms