C++에서 인접 요소를 고려하지 않고 배열의 최대 세트 비트 합계

이 문제에서는 정수 배열 arr[]이 제공됩니다. 우리의 임무는 C++에서 인접 요소를 고려하지 않고 배열의 최대 설정 비트 합계를 계산하는 프로그램을 만드는 것입니다.

문제 설명 − 여기에 배열 arr[]이 있습니다. 각 숫자에 대해 설정된 비트 수를 찾아야 합니다. 그런 다음 배열의 인접한 요소에서 최대 세트 비트 합계를 찾습니다. 즉, [i] + a[i+2]의 최대 합 ….

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {1, 4, 6, 7}

출력

4

설명

요소가 이진 형식인 배열

arr[] = {01, 100, 101, 111}
Bit count array = {1, 1, 2, 3}

대체 비트 수,

arr[0] + arr[2] = 1 + 2 = 3
arr[1] + arr[3] = 1 + 3 = 4

최대 합계 =4.

해결 방법

이 문제를 해결하기 위해 단순히 숫자에서 설정된 비트 수를 찾습니다. 그리고 설정된 비트 수가 최대인 대체 쌍을 찾습니다.

최대 합은 0으로 시작하거나 1로 시작하는 배열에 대한 것입니다. 따라서 우리는 그 중 2개의 대소문자를 확인하기만 하면 됩니다.

우리 솔루션의 작동을 설명하는 프로그램

예

#include<iostream>
using namespace std;
int countSetBit(int n){
   int setBits = 0;
   while(n) {
      setBits++;
      n = n & (n - 1);
   }
   return setBits;
}
int findMaxBitAltSubArray(int arr[], int n){
   int EvenSum = countSetBit(arr[0]);
   int OddSum = 0;
   for (int i = 1; i < n; i++){
      if(i % 2 == 0){
         EvenSum += countSetBit(arr[i]);
      } else {
         OddSum += countSetBit(arr[i]);
      }
   }
   if(EvenSum >= OddSum){
      return EvenSum;
   }
   return OddSum;
}
int main() {
   int arr[] = {1, 4, 6, 7};
   int n = 4;
   cout<<"The maximum set bit sum in the array without considering adjacent elements is "<<findMaxBitAltSubArray(arr, n);
   return 0;
}

출력

The maximum set bit sum in the array without considering adjacent elements
is 4