C++で同じ数のセットビットを持つ数値を加算することによる最大合計

問題の説明

N個の数値の配列が与えられた場合、タスクは、同じセットビット数の数値を加算することによって取得できる最大の合計を見つけることです

例

入力配列が{2、5、8、9、10、7}の場合、出力は14-

• 2のセットビット数は1です

• 5のセットビット数は2です

• 8のセットビット数は1です

• 9のセットビット数は2です

• 10のセットビット数は2です

• 7のセットビット数は3です

その場合、（5 + 9 + 10）の合計は24であり、そのセットビット数は2です

アルゴリズム

• 配列をトラバースし、すべての要素の設定ビット数を数えます。

• 配列を32ビット用に初期化します。この数は、最大32セットビットであると想定しています。

• 配列を反復処理し、配列要素を設定されたビット数を示す位置に追加します。

• トラバースして最大合計を見つけ、それを返します。

例

#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