Sort Integers by The Number of 1 Bits solution and explanation
Google
9 more videos on this problem
Sort Integers by The Number of 1 Bits | 2 Approaches | AMAZON | Leetcode 1356 | codestorywithMIKcodestorywithMIK · 21:46 · 16K views
LC: 1356 | Sort Integers by the number of 1 BitsShrayansh Jain · 11:22 · 2K views
Sort Integers by The Number of 1 Bits - LeetCode #1356 | Heap Solution - PythonCodingNinja · 8:28 · 1K views
Sort Integers by The Number of 1 Bits | LeetCode 1356 | Custom Comparator & Bit CountingSanyam IIT Guwahati · 8:11 · 1K views
1356. Sort Integers by The Number of 1 Bits | Leetcode Daily - PythonLeetcode Daily · 9:26 · 749 views
Sort Integers by The Number of 1 Bits - PythonCheatCode Ninja · 8:07 · 677 views
Daily Leetcode #1308: Oct 30, 2023 - 1356. Sort Integers by The Number of 1 BitsProgramming Live with Larry · 3:52 · 404 views
1356. Sort Integers by The Number of 1 Bits | Made Easy 🔥Code Crusaders · 4:31 · 402 views
Sort Integers by The Number of 1 Bits | LeetCode 1356 | Java Code | Developer CoderDeveloper Coder · 11:59 · 400 views
Sort Integers by The Number of 1 Bits - LeetCode 1356 - PythonAlpha-Code · 15:48 · 329 views
The problem
You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.
Return the array after sorting it.
Example 1:
Input: arr = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7] Explantion: [0] is the only integer with 0 bits. [1,2,4,8] all have 1 bit. [3,5,6] have 2 bits. [7] has 3 bits. The sorted array by bits 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] Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.
Constraints:
1 <= arr.length <= 5000 <= arr[i] <= 104
Approach overview
Problem Overview: Given an array of integers, sort the numbers based on how many 1 bits appear in their binary representation. If two numbers have the same number of set bits, order them by their numeric value.
The task combines Bit Manipulation with Sorting. The core operation is computing the popcount (number of set bits) for each integer and using it as the primary sorting key.
Approach 1: Sorting with Custom Key Function (O(n log n) time, O(1) extra space)
Sort the array using a custom comparator or key function. The key returns a pair: (bitCount(x), x). The first element sorts numbers by the number of set bits. The second element ensures values with the same bit count are ordered numerically. Most languages expose built-in popcount utilities such as bin(x).count('1') in Python, Integer.bitCount() in Java, or __builtin_popcount() in C++. The sorting algorithm handles the ordering once the key is defined. Time complexity is O(n log n) due to sorting, while space complexity is O(1) or O(log n) depending on the sorting implementation.
Approach 2: Counting Bits and Sorting (O(n log n) time, O(n) space)
First compute the bit count for every number and store it alongside the value, typically as pairs like (bitCount, value). Bit counts can be calculated using Kernighan’s algorithm, built-in popcount functions, or simple bit shifting. After building this list, sort it using the pair structure so that the array is ordered by bit count first and number second. Finally extract the sorted numbers back into the result array. The preprocessing pass takes O(n * B) where B is the number of bits (at most 32 for typical integers), followed by sorting in O(n log n). Space complexity becomes O(n) due to the auxiliary array.
Both approaches rely on the same insight: treat the bit count as the primary sorting metric and the integer value as the tie breaker. The problem mainly tests familiarity with Array handling and popcount operations.
Recommended for interviews: The custom key sorting approach is the expected solution. It is concise, leverages built-in popcount functions, and clearly expresses the intended ordering rule. Mentioning how to compute set bits (for example with Kernighan’s trick) shows deeper understanding of bit manipulation even if the implementation uses a built-in method.
Approach 1: Sorting with Custom Key Function
The basic idea is to use a custom key that calculates two parameters for sorting: the number of 1 bits in the binary representation and the integer value itself. This dual-key approach allows us to first sort by the number of 1 bits and then by the integer values in ascending order by default.
def sortByBits(arr):
return sorted(arr, key=lambda x: (bin(x).count('1'), x))import java.util.Arrays;
public static int[] sortByBits(int[] arr) {
return Arrays.stream(arr)
.boxed()
.sorted((a, b) -> Integer.bitCount(a) == Integer.bitCount(b) ? a - b : Integer.bitCount(a) - Integer.bitCount(b))
.mapToInt(i -> i)
.toArray();
}#include <vector>
#include <algorithm>
std::vector<int> sortByBits(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end(), [](int a, int b) {
int countA = __builtin_popcount(a);
int countB = __builtin_popcount(b);
return countA == countB ? a < b : countA < countB;
});
return arr;
}This solution uses Python's built-in sorted function with a custom key. bin(x).count('1') counts the number of 1 bits in the binary representation, and we sort the array using a tuple as the key where the first element is the number of 1 bits and the second element is the number itself.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the sorted array.
Approach 2: Counting Bits and Sorting
Another approach is to first count the number of 1 bits for each integer and create a pair of this count and the integer. Then, sort the array of these pairs according to the count and original value.
function sortByBits(arr) {
return arr.sort((a, b) => {
const countA = a.toString(2).split('1').length - 1;
const countB = b.toString(2).split('1').length - 1;
if (countA === countB) return a - b;
return countA - countB;
});
}#include <stdio.h>
#include <stdlib.h>
int countBits(int n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
int compare(const void *a, const void *b) {
int countA = countBits(*(int *)a);
int countB = countBits(*(int *)b);
if (countA == countB)
return (*(int *)a - *(int *)b);
return countA - countB;
}
void sortByBits(int* arr, int arrSize) {
qsort(arr, arrSize, sizeof(int), compare);
}using System;
using System.Linq;
public class Solution {
public int[] SortByBits(int[] arr) {
return arr.OrderBy(x => Convert.ToString(x, 2).Count(c => c == '1')).ThenBy(x => x).ToArray();
}
}This JavaScript solution uses the Array.sort method with a custom comparator. It calculates the count of 1's by converting the number to binary and counting the 1's using string manipulation.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1), sorting is done in place.
Approach 3: Custom Sorting
We sort the array arr according to the requirements of the problem, that is, sort in ascending order according to the number of 1s in the binary representation. If there are multiple numbers with the same number of 1s in the binary representation, they must be sorted in ascending order by numerical value.
The time complexity is O(n log n), and the space complexity is O(n). Where n is the length of the array arr.
function sortByBits(arr: number[]): number[] {
const n = arr.length;
for (let i = 0; i < n; ++i) {
arr[i] += bitCount(arr[i]) * 100000;
}
arr.sort((a, b) => a - b);
for (let i = 0; i < n; ++i) {
arr[i] %= 100000;
}
return arr;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func sortByBits(arr []int) []int {
for i, v := range arr {
arr[i] += bits.OnesCount(uint(v)) * 100000
}
sort.Ints(arr)
for i := range arr {
arr[i] %= 100000
}
return arr
}impl Solution {
pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
let n = arr.len();
for i in 0..n {
arr[i] += arr[i].count_ones() as i32 * 100000;
}
arr.sort();
for i in 0..n {
arr[i] %= 100000;
}
arr
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting with Custom Key Function | Time Complexity: O(n log n) due to the sorting operation. |
| Counting Bits and Sorting | Time Complexity: O(n log n) for sorting. |
| Custom Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Custom Key (popcount) | O(n log n) | O(1) - O(log n) | Best general solution. Uses built-in bit count and concise comparator. |
| Counting Bits then Sorting Pairs | O(n log n) | O(n) | Useful when computing or caching bit counts separately before sorting. |
Frequently asked questions
Is Sort Integers by The Number of 1 Bits easy or hard?
The problem is classified as Easy because the core idea is straightforward once you recognize that sorting should use the bit count as a key. Most of the work is using a popcount function and defining the correct comparator. It mainly checks familiarity with bit operations and custom sorting.
Sort Integers by The Number of 1 Bits Python/Java solution
In Python, sort the list with key=lambda x: (bin(x).count('1'), x). In Java, use Arrays.sort with a comparator that compares Integer.bitCount(a) and Integer.bitCount(b), then compares the numbers if counts match. Both implementations run in O(n log n) time.
How to solve Sort Integers by The Number of 1 Bits in O(n)?
Pure O(n) ordering is generally not used because comparison-based sorting dominates the runtime. A near-linear strategy can group numbers by their bit counts using buckets and then sort each bucket by value. Even then, ordering within buckets typically requires sorting, so the practical complexity remains around O(n log n).
What is the best approach for Sort Integers by The Number of 1 Bits?
The most practical approach sorts the array using a custom key that returns (bitCount(x), x). The bit count determines the primary ordering, and the integer value breaks ties. Built-in functions like Python's bin(x).count('1') or Java's Integer.bitCount make this straightforward. The overall complexity is O(n log n) due to sorting.
Is Sort Integers by The Number of 1 Bits asked at Google/Amazon/Meta?
Bit manipulation and custom sorting problems like this appear in interviews at companies such as Amazon and Google. The problem tests understanding of popcount operations, comparator design, and stable ordering rules. Interviewers often expect candidates to quickly identify the (bitCount, value) sorting key.
What data structure is used in Sort Integers by The Number of 1 Bits?
The main data structure is an array that gets reordered using a sorting algorithm. Some implementations also use auxiliary pairs or tuples like (bitCount, value) to simplify comparisons. The key operation relies on bit manipulation to compute the number of set bits in each integer.
What is the time complexity of Sort Integers by The Number of 1 Bits?
The dominant cost is sorting the array, which takes O(n log n) time. Computing the number of set bits for each element is O(B) where B is the bit length of the integer (typically up to 32), making it effectively constant. Overall complexity remains O(n log n) with O(1) to O(n) auxiliary space depending on the implementation.