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

Source: Dev.to

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:

1. The count of 1s in their binary form.
2. The number itself.

Think of it like sorting people by the number of buttons on their shirt; if two people have the same number of buttons, we then look at their height to break the tie. In code, we use bit‑manipulation functions (or built‑in helpers) to count bits, then sort primarily by that count and secondarily by the integer value.

Walkthrough: Understanding the Examples

Example 1

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8]

Count the 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 sortByBits(vector& arr) {
        // Custom comparator using ranges::sort
        // Sorts by bit count first, then by the value of 'a'
        ranges::sort(arr, ranges::less{}, [](const int a) {
            const int bitCount = bitset(a).count();
            return pair{bitCount, a};
        });
        return arr;
    }
};

Python

class Solution:
    def sortByBits(self, arr: list[int]) -> list[int]:
        # Python's sort is stable. 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 let you define a “key” or a “comparator” function to control sorting logic.
• 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 more flexible developer when tackling complex data structures.