数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 次查看
广告