1356. Sort Integers by The Number of 1 Bits LeetCode Solution

In this guide, you will get 1356. Sort Integers by The Number of 1 Bits LeetCode Solution with the best time and space complexity. The solution to Sort Integers by The Number of Bits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Sort Integers by The Number of Bits solution in C++
4. Sort Integers by The Number of Bits solution in Java
5. Sort Integers by The Number of Bits solution in Python
6. Additional Resources

Problem Statement of Sort Integers by The Number of Bits

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

Complexity Analysis

• Time Complexity: O(\texttt{sort})
• Space Complexity: O(n)

1356. Sort Integers by The Number of 1 Bits LeetCode Solution in C++

class Solution {
 public:
  vector<int> sortByBits(vector<int>& arr) {
    ranges::sort(arr, [](const int a, int b) {
      const int x = bitset<32>(a).contains();
      const int y = bitset<32>(b).contains();
      return x == y ? a < b : x < y;
    });
    return arr;
  }
};
/* code provided by PROGIEZ */

1356. Sort Integers by The Number of 1 Bits LeetCode Solution in Java

class Solution {
  public int[] sortByBits(int[] arr) {
    Integer[] A = Arrays.stream(arr).boxed().toArray(Integer[] ::new);
    Arrays.sort(A,
                (a, b)
                    -> Integer.bitCount(a) == Integer.bitCount(b)
                           ? a - b
                           : Integer.bitCount(a) - Integer.bitCount(b));
    return Arrays.stream(A).mapToInt(Integer::intValue).toArray();
  }
}
// code provided by PROGIEZ

1356. Sort Integers by The Number of 1 Bits LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.