1356. Sort Integers by The Number of 1 Bits
Problem Description
The problem presents a task where we are given an array of integers, arr
, and we need to sort this array with a specific set of rules based on the binary representation of its elements. The primary sorting criterion is the number of 1
s in the binary representation of each integer. If two integers have the same number of 1
s, then they should be sorted in ascending order according to their integer values.
The goal is to return the array sorted first by the number of 1
s in their binary representation, and then by their value when there's a tie on the first criteria.
Intuition
To tackle the sorting problem, we need to decide upon a sorting strategy that complies with the rules provided:
- Count the number of
1
s in the binary representation of each integer. - Sort the integers by the number of
1
s. In the event of a tie (when two numbers have the same number of1
s), sort by the integer values themselves, in ascending order.
The built-in Python sorted
function offers us a straightforward way to sort the elements of an array. We can customize the sorting order by providing a key
argument that transforms each element before comparison during the sort. This transformation doesn't change the actual elements of the array, but it is used to guide the sort order.
Thus, we choose a lambda
function as the key
, that returns a tuple for each x
in arr
: (x.bit_count(), x)
. The bit_count
method returns the number of 1
s in the binary representation of x
, which addresses our primary criterion. By creating a tuple with x.bit_count()
as the first element and x
as the second, we ensure that when two numbers have the same number of 1
s, the smaller number comes first, satisfying the secondary sorting criterion.
The sorted list according to these criteria will thus be the result we return.
Learn more about Sorting patterns.
Solution Approach
The provided Python solution makes use of Python's higher-level functionality to implement the sorting logic cleanly and efficiently. To understand the solution's implementation, let's break down the key components and the patterns leveraged in the code:
Lambda Functions
A lambda function is an anonymous function defined with the lambda
keyword in Python. In the solution, the lambda function is used as a key
argument to the sorted
function. It defines the sorting behavior according to the specific problem constraints.
Tuple Sorting
The lambda
function leverages a feature of Python's sorting algorithm, which can sort tuples lexicographically. That means the first elements of the tuples are compared first, and if those are equal, the second elements are compared, and so on.
bit_count
Method
The bit_count()
method returns the number of 1
bits in the binary representation of an integer (an important note here is that this method is only available in Python 3.10 or later). If you're using an earlier version of Python, you would need to use the bin(x).count('1')
approach instead.
Sorted Function
Finally, the sorted
function is a built-in Python function that returns a new list containing all items from the iterable in ascending order. A key feature of sorted
is that it allows you to define a key
function that is called on each element before making comparisons.
Now, let's piece everything together. The solution approach is carried out as follows:
-
Define a Key Function: The
lambda
function(lambda x: (x.bit_count(), x))
generates a tuple with two items for each elementx
in the arrayarr
. The first item is the count of1
s in the binary representation ofx
, and the second item isx
itself. -
Apply Sorting with Custom Key: The
sorted
function then uses the tuples generated by thelambda
function to sort the entire array. It prioritizes the count of1
bits first, as it's the first element of the tuple. If two tuples have the same first element (meaning the elements have the same number of1
s in their binary representations), the second element of the tuple (the element's value) is used as a tie-breaker. -
Return the Sorted Array: The
sorted
function does not modifyarr
in place; instead, it returns a new list, which is the correctly sorted version ofarr
as per the problem's constraints.
By combining these Python features, the solution elegantly and efficiently sorts the array arr
according to the problem's specifications.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an array of integers for demonstration: arr = [3, 1, 2, 4]
.
First, we'll determine the binary representation of each number and count the number of 1
s:
- The binary representation of
3
is11
, which has2
ones. - The binary representation of
1
is1
, which has1
one. - The binary representation of
2
is10
, which has1
one. - The binary representation of
4
is100
, which has1
one.
Following the primary sorting criterion (number of 1
s), we'd have an intermediate sort order of [1, 2, 4]
(each with one 1
), and [3]
(with two 1
s). But since 1
, 2
, and 4
all have the same number of 1
s in their binary representation, we must sort them by their value.
The custom lambda
function used as the key
in the sorted
algorithm will generate the following tuples based on the binary count and the integer value:
- For
3
:(2, 3)
- For
1
:(1, 1)
- For
2
:(1, 2)
- For
4
:(1, 4)
When we pass these tuples to the sorted
function, it will sort the numbers first by the number of 1
s in their binary representation, and then by their integer value in case of a tie.
Here is what the sorting stage looks like with these tuples:
(1, 1)
comes before(1, 2)
and(1, 4)
because their first elements are equal and1
is the smallest integer value among them.(1, 2)
comes before(1, 4)
because they have the same number of1
s and2
is smaller than4
.(2, 3)
comes after all(1, x)
tuples because2
is greater than1
.
As a result, considering the second element of each tuple, we get the sorted array: [1, 2, 4, 3]
.
The return value of the sorted
function with the custom lambda
function as the provided key will give us this final sorted array which satisfies both the primary and secondary sorting criteria specified in the problem.
Solution Implementation
1class Solution:
2 def sort_by_bits(self, arr: List[int]) -> List[int]:
3 # Sort the array based on the number of 1's in the binary representation
4 # of each number ('x.bit_count()'). In the event of a tie, the numbers
5 # are sorted based on their value ('x').
6 return sorted(arr, key=lambda x: (bin(x).count('1'), x))
7 # Note: The use of 'x.bit_count()' is available in Python 3.10 and later.
8 # For versions before Python 3.10, we can use 'bin(x).count('1')' instead.
9
10# Example usage:
11# solution = Solution()
12# result = solution.sort_by_bits([0,1,2,3,4,5,6,7,8])
13
1import java.util.Arrays; // Importing Arrays class for sort function
2
3class Solution {
4 public int[] sortByBits(int[] arr) {
5 int n = arr.length; // Store the length of the array
6
7 // Add to each element in the array a value that represents
8 // the bit count of the number multiplied by 100000 to ensure
9 // it is prioritized in the sorting
10 for (int i = 0; i < n; ++i) {
11 int bitCount = Integer.bitCount(arr[i]); // Count number of 1-bits in arr[i]
12 arr[i] += bitCount * 100000; // Add 100000 for each 1-bit to prioritize in sorting
13 }
14
15 Arrays.sort(arr); // Sort the array with modified values
16
17 // After sorting retrieve the original values by taking modulo 100000
18 for (int i = 0; i < n; ++i) {
19 arr[i] %= 100000; // Reduce each element back to original value
20 }
21
22 return arr; // Return the sorted array by bits
23 }
24}
25
1class Solution {
2public:
3 // Function to sort the numbers based on the number of 1-bits they have.
4 // In case of a tie, sort by the values themselves.
5 vector<int> sortByBits(vector<int>& arr) {
6 // Apply a transformation to each number in the array.
7 // The transformation adds the number of 1-bits in the number times 100000
8 // to the number itself. This is done to couple the number of 1-bits with the number.
9 for (int& num : arr) {
10 num += __builtin_popcount(num) * 100000;
11 }
12
13 // Sort the transformed array.
14 // The numbers are now ordered first by the number of 1-bits, then by the number's value.
15 sort(arr.begin(), arr.end());
16
17 // Iterate through the array to revert the transformation and obtain
18 // the original numbers, preserving the new order.
19 for (int& num : arr) {
20 num %= 100000; // Remove the added portion to get back the original number.
21 }
22
23 // Return the sorted array.
24 return arr;
25 }
26};
27
1// Function to sort an array of numbers based on the number of 1-bits each number has.
2// In the case of a tie, numbers are sorted by their value.
3function sortByBits(arr: number[]): number[] {
4 // Helper function to count the number of 1-bits in a binary representation of a number.
5 const countBits = (num: number): number => {
6 let count = 0;
7 while (num) {
8 // Remove the rightmost 1-bit from the number
9 num &= num - 1;
10 // Increment the count of 1-bits
11 count++;
12 }
13 return count;
14 };
15
16 // Sorting the array based on the number of 1-bits each number has (asc order).
17 // In the case of a tie, sort by numerical value (asc order).
18 return arr.sort((a, b) => {
19 // First, compare by the number of 1-bits
20 const bitCountComparison = countBits(a) - countBits(b);
21 if (bitCountComparison !== 0) {
22 return bitCountComparison;
23 }
24 // If the number of 1-bits is the same, compare by the numbers themselves
25 return a - b;
26 });
27}
28
Time and Space Complexity
Time Complexity
The time complexity of the provided code primarily depends on the complexity of the sorting algorithm used by Python's sorted
function. Python uses the TimSort algorithm, which has a time complexity of O(n log n)
for the average and worst case, where n
is the number of elements in the array to be sorted.
In this case, for each comparison, the sorting algorithm also calculates the bit count (number of 1s in the binary representation of the number), which is O(1)
as Python's integer bit count implementation is efficient and not based on the value of the number but the number of set bits. However, this bit count operation will be performed multiple times per element during the sorting process.
Thus, assuming k
is the number of comparisons performed by the sorting algorithm, the total time complexity considering the bit count operations for comparison purposes becomes O(k)
. Since k
can be as large as n log n
comparisons, the total time complexity remains O(n log n)
.
Space Complexity
The space complexity of this function is O(n)
, as the sorted
function returns a new list containing the sorted elements and does not sort the list in place. Hence, a new array of the same size as the input array is created.
Additionally, there is no significant extra space used during the sorting process, except for the temporary variables used in the lambda function during comparison, so the space complexity due to the lambda function remains constant, O(1)
. Combining these, the overall space complexity remains O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first