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

更新于: 2020年1月30日

240 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告