C++で隣接する要素を考慮しない配列の最大セットビット合計

この問題では、整数の配列arr[]が与えられます。私たちのタスクは、C ++の隣接する要素を考慮せずに、配列の最大セットビット合計を計算するプログラムを作成することです。

問題の説明 −ここに、配列arr[]があります。各数値のセットビット数を見つける必要があります。次に、配列の隣接する要素の最大セットビット合計を見つけます。つまり、a [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