# Sort Integers by The Number of 1 Bit Leetcode Solution

Difficulty Level Easy
algorithms Bit Manipulation coding Interview interviewprep LeetCode LeetCodeSolutions SortingViews 5295

## Problem statement

In the problem ” Sort Integers by The Number of 1 Bit,” we are given an array arr. Our task is to sort the elements in the array according to the number of 1 bit in the binary representation of the number in ascending order.

If two or more number contains an equal number of 1 bit in their binary representation, in that case we need to sort them in increasing order. arr[i] lies between 0 and 10000.

### Example

`arr=[7,1,6,5]`
`[1,5,6,7]`

Explanation:

The binary representation of each number in the array: 7 contains 3 one bit.

1 contains 1 one bit.

6 contains 6 one bit.

5 contains 5 one bit.

so after sorting according to the condition it becomes: [ 1,5,6,7].

## Approach for Sort Integers by The Number of 1 Bit Leetcode Solution

The very basic approach to solve this problem is to count the number of 1 bit in each element of the array and then use a comparator function to sort the array. The comparator function compares two elements. If both elements contain a different number of 1 bit then the number which contains less number of 1 bit comes first else smaller number comes first.

We can solve this problem even in a smarter way. As we already know arr[i] lies between 0 and 10000. We can store both the number of one bit and the value of arr[i] in arr[i] itself. For this, we will multiply the number of 1 bit in arr[i] with 10001 and add arr[i]. This basically looks like this:

arr[i]=arr[i]+10001*(number of 1 bit in arr[i])

Now we will sort the array. As we need to return the sorted array so we will store arr[i]%10001 in arr[i] and then return the array.

### C++ code for Sort Integers by The Number of 1 Bit

```#include <bits/stdc++.h>
using namespace std;
vector<int> sortByBits(vector<int>& arr) {
int n=arr.size();
for(int i=0;i<n;i++)
arr[i]+=10001*__builtin_popcount(arr[i]);
sort(arr.begin(),arr.end());
for(int i=0;i<n;i++)
arr[i]=arr[i]%10001;
return arr;
}
int main()
{
vector<int> arr = {7,1,6,5};
vector<int>ans=sortByBits(arr);
for(int i=0;i<arr.size();i++)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}```
`[1,5,6,7]`

### Java code for Sort Integers by The Number of 1 Bit

```import java.util.Arrays;
public class Tutorialcup {
public static int[] sortByBits(int[] arr) {
int n=arr.length;
for(int i=0;i<n;i++)
arr[i]+=10001*Integer.bitCount(arr[i]);
Arrays.sort(arr);
for(int i=0;i<n;i++)
arr[i]=arr[i]%10001;
return arr;
}
public static void main(String[] args) {
int [] arr = {7,1,6,5};
int[]ans=sortByBits(arr);
System.out.println(Arrays.toString(ans));
}
}```
`[1,5,6,7]`

## Complexity Analysis of Sort Integers by The Number of 1 Bit Leetcode Solution

### Time complexity

The time complexity of the above code is O(n) because we are traversing the given arr array only once. Here n is the length of the given arr array.

### Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References

Translate »