1356. Sort Integers by The Number of 1 Bits

EasyBit ManipulationArrayCountingSorting
Leetcode Link

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 1s in the binary representation of each integer. If two integers have the same number of 1s, 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 1s 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:

  1. Count the number of 1s in the binary representation of each integer.
  2. Sort the integers by the number of 1s. In the event of a tie (when two numbers have the same number of 1s), 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 1s 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 1s, 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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:

  1. Define a Key Function: The lambda function (lambda x: (x.bit_count(), x)) generates a tuple with two items for each element x in the array arr. The first item is the count of 1s in the binary representation of x, and the second item is x itself.

  2. Apply Sorting with Custom Key: The sorted function then uses the tuples generated by the lambda function to sort the entire array. It prioritizes the count of 1 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 of 1s in their binary representations), the second element of the tuple (the element's value) is used as a tie-breaker.

  3. Return the Sorted Array: The sorted function does not modify arr in place; instead, it returns a new list, which is the correctly sorted version of arr 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example 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 1s:

  • The binary representation of 3 is 11, which has 2 ones.
  • The binary representation of 1 is 1, which has 1 one.
  • The binary representation of 2 is 10, which has 1 one.
  • The binary representation of 4 is 100, which has 1 one.

Following the primary sorting criterion (number of 1s), we'd have an intermediate sort order of [1, 2, 4] (each with one 1), and [3] (with two 1s). But since 1, 2, and 4 all have the same number of 1s 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 1s 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, 1) comes before (1, 2) and (1, 4) because their first elements are equal and 1 is the smallest integer value among them.
  2. (1, 2) comes before (1, 4) because they have the same number of 1s and 2 is smaller than 4.
  3. (2, 3) comes after all (1, x) tuples because 2 is greater than 1.

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
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement recursion?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Sorting Summary

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫