ผลรวมบิตสูงสุดที่กำหนดในอาร์เรย์โดยไม่คำนึงถึงองค์ประกอบที่อยู่ติดกันใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม งานของเราคือสร้างโปรแกรมเพื่อคำนวณผลรวมบิตสูงสุดของชุดข้อมูลในอาร์เรย์โดยไม่ต้องพิจารณาองค์ประกอบที่อยู่ติดกันใน C++

คำอธิบายปัญหา − ที่นี่ เรามีอาร์เรย์ arr[] เราต้องหาจำนวน set bit ของแต่ละจำนวน จากนั้น เราจะหาผลรวมบิตสูงสุดในองค์ประกอบที่อยู่ติดกันของอาร์เรย์ เช่น ผลรวมสูงสุดของ 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.

แนวทางการแก้ปัญหา

เพื่อแก้ปัญหานี้ เราจะเพียงแค่หาจำนวนบิตที่ตั้งไว้เป็นตัวเลขนั้น และหาคู่สำรองที่มีจำนวน set bit สูงสุด

ผลรวมสูงสุดจะเป็นสำหรับอาร์เรย์ที่ขึ้นต้นด้วย 0 หรือเริ่มต้นด้วย 1 ดังนั้นเราต้องตรวจสอบกรณีของสองตัวนี้

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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