344. Sort an Array According to Count of Set Bits

Given an array of n non-negative integers, sort it so that elements with a higher count of set bits (1s in binary) come first. Elements with an equal set-bit count must keep their original relative order (i.e. the sort must be stable).

Input: The first line contains an integer n. The second line contains n space-separated non-negative integers, the array. Output: Print the array reordered by decreasing set-bit count, keeping original relative order among equal counts, space-separated, on one line.

1 <= n <= 10^5, 0 <= arr[i] <= 10^9

Stability is the whole crux of this problem's difficulty - without the stability requirement, this would just be an ordinary custom-key sort; make sure whatever sort you use is genuinely guaranteed stable, not just 'usually appears to preserve order' by coincidence.

Every number can be written in binary (1s and 0s). Count how many 1s each number has, then arrange the whole list so numbers with MORE 1s come first. If two numbers tie on the count, keep them in whatever order they originally appeared. Brute force: Manually count each number's set bits by repeatedly checking its last bit and shifting right, then use any simple comparison-based sort - correct, but you must be careful to use a genuinely STABLE sort, or ties will be reordered incorrectly. Optimised: Most languages provide a fast built-in popcount function (or you compute it once per element in O(log(max value)) time), and pairing each value with its popcount before feeding it into a stable sort (keyed only on popcount, descending) handles the tie-breaking requirement automatically and correctly, with no extra bookkeeping needed on your part.

Compute the popcount (number of set bits) of every element, then run insertion sort using popcount as the comparison key, only ever moving an element past another when its bit count is strictly greater (never on a tie). Insertion sort naturally never reorders equal keys relative to each other, so stability is automatic, but its nested shifting makes it quadratic. Time: O(n^2) Space: O(1)

Since values fit in about 30 bits, popcount only ever ranges from 0 to 30 - a small, bounded set of keys. Create a bucket (list) for every possible popcount value, walk the array once appending each element to the bucket for its popcount (which preserves original order within each bucket automatically), and then concatenate the buckets from highest popcount to lowest. This is a counting/bucket sort that is inherently stable and processes the array in linear time instead of paying a logarithmic sorting factor. Time: O(n) Space: O(n)

Precompute each element's popcount, pair it with its original index, and sort these pairs with a stable O(n log n) algorithm such as merge sort, comparing by popcount descending and falling back to original index ascending to preserve relative order on ties. This scales far better than insertion sort for the given n up to 10^5 while still guaranteeing stability through the explicit index tiebreak. Time: O(n log n) Space: O(n)

1. For each number in the array, count its set bits (the number of 1s in its binary representation) - this is called its 'popcount'. 2. Pair each number with its popcount and its original position in the array. 3. Sort these pairs by popcount in DECREASING order. 4. For any tie in popcount, preserve the original relative order (this is exactly what 'stable' sorting guarantees automatically).

Time: Computing popcounts for every element takes time proportional to the number of elements times the number of bits in each number; the sort itself takes n log n - overall, it's dominated by the sorting step for realistically-sized inputs. Space: O(n), to store each element alongside its computed popcount before sorting.

a value of 0 (zero set bits, sorts to the end); multiple elements sharing the same set-bit count, which must keep their original relative order - as in the example, 5 and 3 both have two set bits and 5 stays before 3; n = 10^5 for performance.

This problem is really testing two separate skills at once: knowing how to count set bits efficiently, AND knowing that stability matters for a correct tie-breaking rule - many candidates get the popcount logic right but use an unstable sort and fail the tie-breaking requirement.