Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 30

Description

Sort Integers by The Number of 1 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

Solution

const int M1  = 0X55555555; // 01010101010101010101010101010101
const int M2  = 0X33333333; // 00110011001100110011001100110011
const int M4  = 0X0F0F0F0F; // 00001111000011110000111100001111
const int M8  = 0X00FF00FF; // 00000000111111110000000011111111
const int M16 = 0X0000FFFF; // 00000000000000001111111111111111
constexpr int popcount(int x) { 
  x = (x & M1) + ((x >> 1) & M1);
  x = (x & M2) + ((x >> 2) & M2);
  x = (x & M4) + ((x >> 4) & M4);
  x = (x & M8) + ((x >> 8) & M8);
  x = (x & M16) + ((x >> 16) & M16);
  return x;
}
class Solution {
public:
  vector<int> sortByBits(vector<int>& arr) {
    sort(arr.begin(), arr.end(), [](int a, int b) {
      int ba = popcount(a);
      int bb = popcount(b);
      return ba < bb || (ba == bb && a < b); 
    });
    return arr;
  }
};

// Accepted
// 77/77 cases passed (6 ms)
// Your runtime beats 76.61 % of cpp submissions
// Your memory usage beats 66.29 % of cpp submissions (10.5 MB)