🍁 Beginner-Friendly Guide 'Sort Integers by The Number of 1 Bits' - Problem 1356 (C++, Python, JavaScript)

#programming #cpp #python #javascript

Sorting is a fundamental skill in programming, but often we need to sort data based on more than just the value of a number. In this guide, we will explore how to reorganize an array based on the hidden binary characteristics of its elements. This approach is common when optimizing low level data processing or working with bit manipulation.

Problem Summary

You're given:
An array of integers called arr.

Your goal:
Sort the integers in ascending order based on the number of set bits (1s) in their binary representation. If two numbers have the same number of 1s, sort them by their actual numerical value in ascending order.

Intuition

The core of this problem lies in "custom sorting." Instead of comparing two numbers directly, we first transform them into a pair of values: the count of 1s in their binary form and the number itself.

Think of it like sorting people in a line. If we sort them by the number of buttons on their shirt, and two people have three buttons, we then look at their height to break the tie. In computer science, we use bit manipulation or built-in library functions to count these "bits." Once we have the bit count, we prioritize that count for the primary sort and use the integer value for the secondary sort.

Walkthrough: Understanding the Examples

Let's look at Example 1: arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]

Count the bits:
0 is 0000 (0 bits)
1 is 0001 (1 bit)
2 is 0010 (1 bit)
4 is 0100 (1 bit)
8 is 1000 (1 bit)
3 is 0011 (2 bits)
5 is 0101 (2 bits)
6 is 0110 (2 bits)
7 is 0111 (3 bits)
Apply Primary Sort (Bit Count):
Group 0 (0 bits), Group 1 (1, 2, 4, 8), Group 2 (3, 5, 6), Group 3 (7).
Apply Secondary Sort (Value):
Within Group 1, the numbers are already in order (1, 2, 4, 8). If they were [8, 2, 4, 1], we would rearrange them to [1, 2, 4, 8].
Final Result: [0, 1, 2, 4, 8, 3, 5, 6, 7]

Code Blocks

C++

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        // We use a custom comparator with ranges::sort
        // It sorts by bit count first, then by the value of 'a'
        ranges::sort(arr, ranges::less{}, [](const int a) {
            const int bitCount = bitset<32>(a).count();
            return pair<int, int>{bitCount, a};
        });
        return arr;
    }
};

Python

class Solution:
    def sortByBits(self, arr: list[int]) -> list[int]:
        # Python's sort is stable. We can sort by a tuple: (bit_count, value)
        # bin(n).count('1') counts the number of 1s in the binary string
        arr.sort(key=lambda x: (bin(x).count('1'), x))
        return arr

JavaScript

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var sortByBits = function(arr) {
    return arr.sort((a, b) => {
        // Count bits using a helper or bitwise trick
        const countA = countSetBits(a);
        const countB = countSetBits(b);

        // If bit counts are equal, sort by numeric value
        if (countA === countB) {
            return a - b;
        }
        // Otherwise, sort by bit count
        return countA - countB;
    });
};

// Helper function to count bits using bitwise operations
function countSetBits(n) {
    let count = 0;
    while (n > 0) {
        n &= (n - 1); // Clears the least significant bit
        count++;
    }
    return count;
}

Key Takeaways

Custom Comparators: Most modern languages allow you to define a "key" or a "comparator" function to change how sorting logic is applied.
Bit Manipulation: Understanding how numbers are stored in binary is essential for low level optimization and specific interview problems.
Stability and Tie-Breaking: When sorting, always consider how to handle items that are "equal" according to your primary criteria.

Final Thoughts

This problem is a classic example of why understanding the underlying binary structure of data matters. While it might seem abstract, this type of logic is frequently used in Cryptography and Data Compression, where the efficiency of bit storage is paramount. Mastering the ability to sort by derived properties (like bit counts) will make you a much more flexible developer when tackling complex data structures.

DEV Community