Đề bài
Cho mảng N số, tìm tổng lớn nhất có được bằng cách cộng các số có cùng số bit đặt (set bits).
Ví dụ
Mảng {2, 5, 8, 9, 10, 7} cho kết quả 24 –
- Số bit đặt của 2 là 1
- Số bit đặt của 5 là 2
- Số bit đặt của 8 là 1
- Số bit đặt của 9 là 2
- Số bit đặt của 10 là 2
- Số bit đặt của 7 là 3
Tổng (5 + 9 + 10) = 24 với số bit đặt = 2.
Thuật toán
- Duyệt mảng, đếm số bit đặt cho mỗi phần tử.
- Khởi tạo mảng 32 bit, giả sử số có tối đa 32 bit đặt.
- Duyệt mảng, cộng phần tử vào vị trí chỉ số bit đặt.
- Duyệt tìm tổng lớn nhất và trả về.
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 << "Tổng lớn nhất = " << maxSum(arr, n) << endl; return 0; }Kết quả
Tổng lớn nhất = 24