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