1356. Sort Integers by The Number of 1 Bits | LeetCode Solution
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
class Solution
{
public:
static int count_set_bits(int n)
{
int ans = 0;
for (int i = 0; i < 32; i++)
{
if (n % 2 == 1)
ans++;
n >>= 1;
}
return ans;
}
static bool comp(int &a, int &b)
{
if (count_set_bits(a) < count_set_bits(b))
return true;
else if (count_set_bits(a) == count_set_bits(b) and a < b)
return true;
else
return false;
}
vector<int> sortByBits(vector<int> &arr)
{
sort(arr.begin(), arr.end(), comp);
return arr;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.