Table of Contents

## 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.

### Implementation

### 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.