Sort Integers by The Number of 1 Bit Leetcode Solution

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.

References