Tổng số bit đặt tối đa trong mảng mà không tính đến các phần tử liền kề trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] các số nguyên. Nhiệm vụ của chúng tôi là tạo chương trình để tính toán Tổng số bit tối đa được đặt trong mảng mà không cần xem xét các phần tử liền kề trong C ++.

Mô tả sự cố - Ở đây, chúng ta có một mảng arr []. Chúng ta phải tìm số bit đặt cho mỗi số. Sau đó, chúng ta sẽ tìm tổng số bit đã đặt lớn nhất trong các phần tử liền kề của mảng. tức là tổng tối đa cho [i] + a [i + 2]….

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

4

Giải thích

Mảng có phần tử ở dạng nhị phân

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

Số lượng bit thay thế,

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

Tổng tối đa =4.

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề này, chúng ta chỉ cần tìm số bit đặt trong số sau đó. Và tìm cặp thay thế có số bit đặt tối đa.

Tổng tối đa sẽ dành cho một mảng bắt đầu bằng 0 hoặc bắt đầu bằng 1. Vì vậy, chúng ta chỉ cần kiểm tra trường hợp của hai trong số chúng.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

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