Skip to main content
Talentd

Sort Integers by The Number of 1 Bits - Solution & Explanation

EasyArrayBit ManipulationSortingCounting11 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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 <= 500
  • 0 <= 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.

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the sorted array.

Try this approach in the editor →

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.

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.

Code

JavaScriptC#C

JavaScript

C#

C

Complexity

Time Complexity: O(n log n) for sorting.
Space Complexity: O(1), sorting is done in place.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting with Custom Key Function

Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the sorted array.

Counting Bits and Sorting

Time Complexity: O(n log n) for sorting.
Space Complexity: O(1), sorting is done in place.

Custom Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 PairsO(n log n)O(n)Useful when computing or caching bit counts separately before sorting.

Video Solution

Sort Integers by The Number of 1 Bits | 2 Approaches | AMAZON | Leetcode 1356 | codestorywithMIK • codestorywithMIK • 16,312 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sort Integers by The Number of 1 Bits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find if Array Can Be Sorted

Next

Find Subsequence of Length K With the Largest Sum