Leetcode 1356. Sort Integers by The Number of 1 Bits

Problem Description

The problem asks us to sort an array of integers. The sorting criteria are in ascending order by the number of 1's in their binary representation and, in case of two or more integers having the same number of 1's, to sort them in ascending order. The binary representation of a number is the number in base 2. For example, the binary representation of 3 is '11', so the number of 1's is 2.

Let's use an example to illustrate this:

If the given array is [0,1,2,3,4,5,6,7,8], then the result should be [0,1,2,4,8,3,5,6,7].

Here is the explanation:

• [0] is the only integer which has 0 bits in its binary representation.
• [1,2,4,8] are the integers that have only 1 bit in their binary representation.
• [3,5,6] are the integers that have 2 bits in their binary representation.
• [7] is the only integer that has 3 bits in its binary representation.

So, when we put them back together in this order, we get the output array [0,1,2,4,8,3,5,6,7].

Approach

The solution for this problem is straightforward. First, we use a sorting algorithm. While sorting, we define our custom comparison function. In the comparison function, we calculate the number of 1's in the binary representation using the bitset data structure. If two numbers have the same number of 1's in the binary representation, we compare the numbers themselves. Finally, we return the sorted array.

Solution

Python

1
2python
3class Solution:
4    def sortByBits(self, arr: List[int]) -> List[int]:
5        arr.sort(key=lambda x: (bin(x).count('1'), x))
6        return arr

In the python solution, the sort() function is used with a custom comparison function. The key argument of sort function expects a function to which each element can be applied. The lambda function lambda x: (bin(x).count('1'), x) is used as the key function which takes an integer from the list and returns a tuple (number of 1's in binary, integer itself).

Java

1
2java
3class Solution {
4    public int[] sortByBits(int[] arr) {
5        Integer[] array = Arrays.stream(arr).boxed().toArray(Integer[]::new);
6        Arrays.sort(array, (a, b) -> Integer.bitCount(a) == Integer.bitCount(b) ? a - b : Integer.bitCount(a) - Integer.bitCount(b));
7        return Arrays.stream(array).mapToInt(Integer::intValue).toArray();
8    }
9}

In the Java solution, we first convert the primitive array to Integer array for using with Arrays.sort() method. This function uses a Comparator function similar to the python solution.

JavaScript

1
2javascript
3var sortByBits = function(arr) {
4    return arr.sort((a,b) => {
5        let aBit = a.toString(2).replace(/0/g, '').length;
6        let bBit = b.toString(2).replace(/0/g, '').length;
7        if( aBit === bBit)
8             return a - b;
9        else
10            return aBit - bBit;
11    });
12};

In the JavaScript solution sort() and toString(2) methods are used to calculate the number of bits for each number.

C++

1
2cpp
3class Solution {
4public:
5    vector<int> sortByBits(vector<int>& arr) {
6        sort(arr.begin(), arr.end(), [](int a, int b) {
7            int countA = __builtin_popcount(a);
8            int countB = __builtin_popcount(b);
9            if(countA == countB)
10                return a < b;
11            return countA < countB;
12        });
13        return arr;
14    }
15};

In C++, the sort() function from the STL is used with a lambda function as custom comparison. __builtin_popcount() is a built-in function of gcc compiler to count set bits in an integer.

C#

1
2csharp
3public class Solution {
4    public int[] SortByBits(int[] arr) {
5        Array.Sort(arr, (a, b) => {
6            int bitCountA = Convert.ToString(a, 2).Count(ch => ch == '1');
7            int bitCountB = Convert.ToString(b, 2).Count(ch => ch == '1');
8
9            if (bitCountA == bitCountB) {
10                return a.CompareTo(b);
11            }
12            return bitCountA.CompareTo(bitCountB);
13        });
14        return arr;
15    }  
16}

In C#, the Array.Sort() method is used along with a custom comparison function defined as a lambda. Convert.ToString(a, 2) is used to convert a number to binary and Count() method is used to count the number of set bits.### Ruby

1
2ruby
3# @param {Integer[]} arr
4# @return {Integer[]}
5def sort_by_bits(arr)
6    arr.sort_by {|a| [a.to_s(2).count('1'), a]}
7end

In Ruby, we use sort_by method to arrange the numbers. The sort_by method uses block of code { |a| [a.to_s(2).count('1'), a] } where we convert each number into binary using to_s(2) method, count the number of 1's with count('1') method. If the count is the same then it falls back to sort by the number itself which is a in { |a| [a.to_s(2).count('1'), a] }.

Rust

1
2rust
3fn sort_by_bits(arr: Vec<i32>) -> Vec<i32> {
4    let mut arr = arr;
5    arr.sort_unstable_by_key(|&x| (x.count_ones(), x));
6    arr
7}

In Rust, we use sort_unstable_by_key method to arrange the numbers. This method rearranges the elements in such a way, but may not maintain the relative order of equal elements. The count_ones is a built-in Rust method that returns the number of ones in the binary representation of an Integer. If the count is equal then numbers are sorted in ascending order.

Kotlin

1
2kotlin
3fun sortByBits(arr: IntArray): IntArray {
4    return arr.sortedWith(compareBy({ Integer.bitCount(it) }, { it })).toIntArray()
5}

In Kotlin, we use sortedWith method in combination with compareBy to sort the array. The Integer.bitCount method is used to get the number of one-bits in the two's complement binary representation of an Integer.

Swift

1
2swift
3func sortByBits(_ arr: [Int]) -> [Int] {
4    return arr.sorted { a, b in
5        let countA = a.nonzeroBitCount
6        let countB = b.nonzeroBitCount
7        return countA == countB ? a < b : countA < countB
8    }
9}

In Swift, we use sorted function with a custom closure that compares the number of ones in the binary representation using the nonzeroBitCount property. If the count is the same, then the integers themselves are compared.

Conclusion: In conclusion, to solve this problem, you can use the inbuilt sort function in each language with a custom comparison function. This function ranks each number by the number of ones in their binary representation and if the number of ones is the same it sorts the numbers by their value.