Sort Integers by The Number of 1 Bits

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.

Examples

Example 1

1
2
3
4
5
6
7
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

1
2
3
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] <= 10^4

Solution

Method 1 - Custom Sorting with Bit Counting

Intuition

Count the number of 1 bits in each number’s binary representation and sort primarily by bit count, secondarily by the number value itself.

Approach

For each number, count the number of 1 bits using bit manipulation
Create pairs of (bit_count, number) or use custom comparator
Sort by bit count first, then by number value for ties
Extract the sorted numbers

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    int countBits(int n) {
        int count = 0;
        while (n) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [this](int a, int b) {
            int bitsA = countBits(a);
            int bitsB = countBits(b);
            if (bitsA == bitsB) {
                return a < b;
            }
            return bitsA < bitsB;
        });
        return arr;
    }
};

// Alternative using __builtin_popcount
class Solution2 {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [](int a, int b) {
            int bitsA = __builtin_popcount(a);
            int bitsB = __builtin_popcount(b);
            if (bitsA == bitsB) {
                return a < b;
            }
            return bitsA < bitsB;
        });
        return arr;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import "sort"

func sortByBits(arr []int) []int {
    countBits := func(n int) int {
        count := 0
        for n > 0 {
            count += n & 1
            n >>= 1
        }
        return count
    }
    
    sort.Slice(arr, func(i, j int) bool {
        bitsI := countBits(arr[i])
        bitsJ := countBits(arr[j])
        if bitsI == bitsJ {
            return arr[i] < arr[j]
        }
        return bitsI < bitsJ
    })
    
    return arr
}

// Alternative using bits.OnesCount
import (
    "math/bits"
    "sort"
)

func sortByBits2(arr []int) []int {
    sort.Slice(arr, func(i, j int) bool {
        bitsI := bits.OnesCount(uint(arr[i]))
        bitsJ := bits.OnesCount(uint(arr[j]))
        if bitsI == bitsJ {
            return arr[i] < arr[j]
        }
        return bitsI < bitsJ
    })
    
    return arr
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;

class Solution {
    private int countBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
    public 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 bitsA = countBits(a);
            int bitsB = countBits(b);
            if (bitsA == bitsB) {
                return Integer.compare(a, b);
            }
            return Integer.compare(bitsA, bitsB);
        });
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = boxed[i];
        }
        
        return arr;
    }
}

// Alternative using Integer.bitCount
class Solution2 {
    public 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 bitsA = Integer.bitCount(a);
            int bitsB = Integer.bitCount(b);
            if (bitsA == bitsB) {
                return Integer.compare(a, b);
            }
            return Integer.compare(bitsA, bitsB);
        });
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = boxed[i];
        }
        
        return arr;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private fun countBits(n: Int): Int {
        var num = n
        var count = 0
        while (num > 0) {
            count += num and 1
            num = num shr 1
        }
        return count
    }
    
    fun sortByBits(arr: IntArray): IntArray {
        return arr.sortedWith { a, b ->
            val bitsA = countBits(a)
            val bitsB = countBits(b)
            when {
                bitsA != bitsB -> bitsA.compareTo(bitsB)
                else -> a.compareTo(b)
            }
        }.toIntArray()
    }
}

// Alternative using countOneBits
class Solution2 {
    fun sortByBits(arr: IntArray): IntArray {
        return arr.sortedWith { a, b ->
            val bitsA = a.countOneBits()
            val bitsB = b.countOneBits()
            when {
                bitsA != bitsB -> bitsA.compareTo(bitsB)
                else -> a.compareTo(b)
            }
        }.toIntArray()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def sortByBits(arr: list[int]) -> list[int]:
    def count_bits(n):
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count
    
    return sorted(arr, key=lambda x: (count_bits(x), x))

# Alternative using bin().count('1')
def sortByBits2(arr: list[int]) -> list[int]:
    return sorted(arr, key=lambda x: (bin(x).count('1'), x))

# Alternative using bit_count() (Python 3.10+)
def sortByBits3(arr: list[int]) -> list[int]:
    return sorted(arr, key=lambda x: (x.bit_count(), x))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
impl Solution {
    pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
        fn count_bits(mut n: i32) -> i32 {
            let mut count = 0;
            while n > 0 {
                count += n & 1;
                n >>= 1;
            }
            count
        }
        
        arr.sort_by(|&a, &b| {
            let bits_a = count_bits(a);
            let bits_b = count_bits(b);
            if bits_a == bits_b {
                a.cmp(&b)
            } else {
                bits_a.cmp(&bits_b)
            }
        });
        
        arr
    }
}

// Alternative using count_ones()
impl Solution2 {
    pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
        arr.sort_by(|&a, &b| {
            let bits_a = a.count_ones();
            let bits_b = b.count_ones();
            if bits_a == bits_b {
                a.cmp(&b)
            } else {
                bits_a.cmp(&bits_b)
            }
        });
        
        arr
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function sortByBits(arr: number[]): number[] {
    function countBits(n: number): number {
        let count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
    return arr.sort((a, b) => {
        const bitsA = countBits(a);
        const bitsB = countBits(b);
        if (bitsA === bitsB) {
            return a - b;
        }
        return bitsA - bitsB;
    });
}

// Alternative using toString(2) and counting '1's
function sortByBits2(arr: number[]): number[] {
    return arr.sort((a, b) => {
        const bitsA = a.toString(2).split('1').length - 1;
        const bitsB = b.toString(2).split('1').length - 1;
        if (bitsA === bitsB) {
            return a - b;
        }
        return bitsA - bitsB;
    });
}

Complexity

⏰ Time complexity: O(n log n + n * k) where n is array length, k is average number of bits (≤ 32)
🧺 Space complexity: O(1) for in-place sorting (O(n) if creating new array)

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 - Custom Sorting with Bit Counting#

Intuition#

Approach#

Code#

Complexity#