Tuyên bố vấn đề
Cho một mảng gồm N số, nhiệm vụ là tìm tổng lớn nhất có thể nhận được bằng cách cộng các số có cùng số bit đã đặt
Ví dụ
Nếu mảng đầu vào là {2, 5, 8, 9, 10, 7} thì đầu ra sẽ là 14 -
-
Số bit đặt trong 2 là 1
-
Số bit đặt trong 5 là 2
-
Số bit đặt trong 8 là 1
-
Số bit đặt trong 9 là 2
-
Số bit đặt trong 10 là 2
-
Số bit đặt trong 7 là 3
Khi đó tổng của (5 + 9 + 10) là 24 có số bit đặt =2
Thuật toán
-
Di chuyển trong mảng và đếm số bit đã đặt cho mọi phần tử.
-
Khởi tạo một mảng cho 32 bit, giả sử số đó có tối đa 32 bit được đặt.
-
Lặp lại trong mảng và thêm phần tử mảng vào vị trí cho biết số lượng bit đã đặt.
-
Duyệt và tìm tổng lớn nhất và trả lại.
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo -
Maximum sum = 24