Sort an array of integers by the number of set bits in each number, breaking ties by numeric order.
Given an array of integers, reorder the elements so that numbers with fewer 1 bits in their binary representation come first. If two numbers have the same number of 1 bits, the smaller numeric value should appear first.
The task is to return the fully sorted array according to this rule.
Input Format
- An integer array
arr. - Each value is treated as a non-negative integer for bit counting.
Output Format
- Return the array sorted by:
- Increasing number of set bits (
1s) in binary. - Increasing numeric value when bit counts are equal.
- Increasing number of set bits (
Constraints
1 <= arr.length- Integers are within a standard 32-bit signed range.
- Assume bit counts are computed on the integer's binary form.
- A comparison-based or custom-key sort is expected.
Example 1
Input
[0,1,2,3,4,5,6,7,8]
Output
[0,1,2,4,8,3,5,6,7]
Explanation
Bit counts: 0->0, 1->1, 2->1, 4->1, 8->1, 3->2, 5->2, 6->2, 7->3. Within equal bit counts, values increase.
Example 2
Input
[10,100,1000,10000]
Output
[10,100,10000,1000]
Explanation
Bit counts are 10->2, 100->3, 10000->5, 1000->6, so the order follows increasing set bits.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.