1356. Sort Integers by The Number of 1 Bits

LeetCode problem link (opens new window)

You are given an integer array arr. Please sort the elements of the array in ascending order of the number of 1s in their binary representation.

If there are multiple numbers with the same number of 1s in their binary representation, they must be sorted in ascending order based on their value.

Please return the sorted array.

Example 1:

• Input: arr = [0,1,2,3,4,5,6,7,8]
• Output: [0,1,2,4,8,3,5,6,7]
• Explanation: [0] is the only number with 0 1s.
  [1,2,4,8] all have 1 1.
  [3,5,6] have 2 1s.
  [7] has 3 1s.
  The sorted array based on the number of 1s is [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 integer in the array has exactly 1 1 in its binary form, so you need to sort them by the numerical value.

Example 3:

• Input: arr = [10000,10000]
• Output: [10000,10000]

Example 4:

• Input: arr = [2,3,5,7,11,13,17,19]
• Output: [2,3,5,17,7,11,13,19]

Example 5:

• Input: arr = [10,100,1000,10000]
• Output: [10,100,10000,1000]

Solution

This problem essentially tests how to calculate the number of 1s in a number's binary representation.

I offer two methods:

• Method 1:

A straightforward approach is to count the number of 1s in each position, looping at most through the number of binary digits of n, up to 32 bits.

int bitCount(int n) {
    int count = 0; // Counter
    while (n > 0) {
        if((n & 1) == 1)  count++;  // If the current bit is 1, increment count
        n >>= 1 ; // Right shift n
    }
    return count;
}

• Method 2

This method loops only as many times as there are 1s in the binary representation of n, making it more efficient than Method 1.

int bitCount(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1); // Clear the lowest set bit
        count++;
    }
    return count;
}

For example, calculating the number of 1s in the binary representation of 12:

Now, I will use Method 2 to solve this problem:

class Solution {
private:
    static int bitCount(int n) { // Calculate the number of 1's in binary representation of n
        int count = 0;
        while(n) {
            n &= (n -1); // Clear the lowest set bit
            count++;
        }
        return count;
    }
    static bool cmp(int a, int b) {
        int bitA = bitCount(a);
        int bitB = bitCount(b);
        if (bitA == bitB) return a < b; // If the number of 1's is the same, compare numerical value
        return bitA < bitB; // Otherwise, compare the count of 1's
    }
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

Versions in Other Languages

Java

class Solution {
    private int cntInt(int val){
        int count = 0;
        while(val > 0) {
            val = val & (val - 1);
            count ++;
        }

        return count;
    }

    public int[] sortByBits(int[] arr) {
      return Arrays.stream(arr).boxed()
            .sorted(new Comparator<Integer>(){
                @Override
                public int compare(Integer o1, Integer o2) {
                    int cnt1 = cntInt(o1);
                    int cnt2 = cntInt(o2);
                    return (cnt1 == cnt2) ? Integer.compare(o1, o2) : Integer.compare(cnt1, cnt2);
                }
            })
            .mapToInt(Integer::intValue)
            .toArray();
    }
}

Python

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        arr.sort(key=lambda num: (self.count_bits(num), num))
        return arr

    def count_bits(self, num: int) -> int:
        count = 0
        while num:
            num &= num - 1
            count += 1
        return count

Go

func sortByBits(arr []int) []int {
    // Whether arr[i] <= arr[j]
    // First compare number of bits, then compare the values themselves
    cmp := func(i, j int) bool {
        c1, c2 := bitCount(arr[i]), bitCount(arr[j])
        if c1 == c2 {
            return arr[i] <= arr[j]
        }
        return c1 <= c2
    }

    // Invoke the library function
    // First argument is the slice to be sorted, second is the comparison function
    sort.Slice(arr, cmp)

    return arr
}

func bitCount(num int) (count int) {
    for num != 0 {
        num &= num-1    // Each operation clears the rightmost set bit
        count++
    }

    return count
}

JavaScript

var sortByBits = function(arr) {
    const bitCount = n =>{// Calculate the number of 1's in n's binary representation
        let count = 0;
        while(n){
            n &= (n - 1);// Clear the lowest set bit
            count++;
        }
        return count;
    }
    // If there's a difference, sort by number of bits; if no difference, sort by original value
    return arr.sort((a,b) => bitCount(a) - bitCount(b) || a - b);
};