Maximum Sum by Adding Numbers with Same Set Bits Count ใน C++

ปัญหา

มีอาร์เรย์ N ตัวเลข หาผลรวมสูงสุดที่ได้จากการบวกตัวเลขที่มีจำนวน Set Bits (บิต 1) เท่ากัน

ตัวอย่าง

Array: {2, 5, 8, 9, 10, 7}
Set bits: 2(1), 5(2), 8(1), 9(2), 10(2), 7(3)
Group set bits=2: 5+9+10 = 24 (Max)

อัลกอริทึม

1. นับ set bits ของแต่ละตัวเลข (ใช้ Brian Kernighan's Algorithm: n &= n-1)
2. สร้างอาร์เรย์ sum[32] เก็บผลรวมของแต่ละกลุ่ม set bits
3. หาค่าสูงสุดใน sum[]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int bitCount(int n){
    int count = 0;
    while (n) { count++; n = n & (n - 1); }
    return count;
}

int maxSum(int arr[], int n){
    int bits[n];
    for (int i = 0; i < n; i++) bits[i] = bitCount(arr[i]);
    int sum[32] = {0};
    for (int i = 0; i < n; i++) sum[bits[i]] += arr[i];
    int maximum = 0;
    for (int i = 0; i < 32; i++) maximum = max(sum[i], maximum);
    return maximum;
}

int main(){
    int arr[] = {2, 5, 8, 9, 10, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum = " << maxSum(arr, n) << endl;
    return 0;
}

ผลลัพธ์

Maximum sum = 24