จำนวนสูงสุดขององค์ประกอบอาร์เรย์ที่อยู่ติดกันโดยมีจำนวนชุดบิตเท่ากันใน C++

เราได้รับอาร์เรย์ขององค์ประกอบจำนวนเต็มที่ไม่ได้เรียงลำดับ และภารกิจคือการคำนวณสองสิ่งที่สำคัญ นั่นคือ

• องค์ประกอบที่มีจำนวนบิตเท่ากัน
• นอกจากนี้ องค์ประกอบที่มีบิตชุดเดียวกันควรมีลักษณะต่อเนื่องกัน

อินพุต

int arr[] = { 5, 8, 1, 2, 9, 12}

ผลผลิต − จำนวนสูงสุดขององค์ประกอบอาร์เรย์ที่อยู่ติดกันโดยมีจำนวนบิตเซ็ตเท่ากันคือ − 3

คำอธิบาย − เราจะคำนวณเลขฐานสองสำหรับองค์ประกอบของอาร์เรย์และคำนวณชุดบิตของพวกมัน

arr[0] = 5 => 0101 => total set bits are -: 2
arr[1] = 8 => 1000 => total set bits are -: 1
arr[2] = 1 => 0001 => total set bits are -: 1
arr[3] = 2 => 0010 => total set bits are -: 1
arr[4] = 9 => 1001 => total set bits are -: 2
Arr[5] = 12 => 1100 => total set bits are -: 2

ดังนั้นองค์ประกอบที่มีจำนวนชุดบิตเท่ากันและยังต่อเนื่องกันในธรรมชาติคือ 5, 9 และ 12 ดังนั้นจำนวนสูงสุดขององค์ประกอบอาร์เรย์ที่อยู่ติดกันซึ่งมีจำนวนบิตชุดเท่ากันคือ 3

ป้อนข้อมูล − int arr[] ={ 5, 8, 1, 2}

ผลผลิต − จำนวนสูงสุดขององค์ประกอบอาร์เรย์ที่อยู่ติดกันโดยมีจำนวนบิตเซ็ตเท่ากันคือ − 2

คำอธิบาย − เราจะคำนวณเลขฐานสองสำหรับองค์ประกอบของอาร์เรย์และคำนวณชุดบิตของพวกมัน

arr[0] = 5 => 0101 => total set bits are -: 2
arr[1] = 8 => 1000 => total set bits are -: 1
arr[2] = 1 => 0001 => total set bits are -: 1
arr[3] = 2 => 0010 => total set bits are -: 1

ดังนั้นอิลิเมนต์ที่มีจำนวนเซตบิตเท่ากันและมีลักษณะต่อเนื่องกันคือ 1 และ 2 ดังนั้นจำนวนอิลิเมนต์อาร์เรย์ที่อยู่ติดกันสูงสุดที่มีจำนวนบิตเซ็ตเท่ากันคือ 2

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนองค์ประกอบอาร์เรย์ของประเภทจำนวนเต็ม

• คำนวณขนาดของอาร์เรย์โดยใช้ฟังก์ชัน size และส่งต่อไปยังฟังก์ชัน

• นำตัวแปรชั่วคราวมาตั้งค่าเป็น 1 และตัวแปรสูงสุดด้วยค่า 1

• สร้างตัวแปร vec ของประเภทเวกเตอร์

• เริ่มการวนซ้ำตั้งแต่ 0 จนถึงขนาดของอาร์เรย์

• คำนวณชุดบิตไบนารีขององค์ประกอบอาร์เรย์โดยใช้ฟังก์ชัน “__builtin_popcount(องค์ประกอบ)” ซึ่งจะคืนค่าจำนวนบิตชุดขององค์ประกอบที่กำหนดที่ส่งผ่านไปยังองค์ประกอบนั้นและเก็บการนับไว้ในเวกเตอร์

• เริ่มวนซ้ำตั้งแต่ 1 จนถึงขนาดของเวกเตอร์

• ภายในเวกเตอร์ ตรวจสอบว่า vec[i+1] =vec[i] แล้วเพิ่มค่า temp ขึ้น 1

• มิฉะนั้น ตั้งค่าอุณหภูมิเป็น 1

• ตั้งค่าสูงสุดด้วยการเลือกค่าสูงสุดระหว่างอุณหภูมิและค่าสูงสุดโดยใช้ฟังก์ชัน maxfunction

• คืนค่าตัวแปรสูงสุด

• พิมพ์ผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
//function to calculate maximum same number of bits
int maximum_SameBits(int arr[], int size){
   int temp = 1;
   int maximum = 1;
   vector<int> vec;
   for (int i = 0; i < size; i++){
      vec.push_back(__builtin_popcount(arr[i]));
   }
   for (int i = 1; i < vec.size(); i++){
      if (vec[i + 1] == vec[i]){
         temp++;
      }
      else{
         temp = 1;
      }
      maximum = max(maximum, temp);
   }
   return maximum;
}
int main(){
   int arr[] = { 5, 8, 1, 2, 9, 12};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum number of contiguous array elements with same number of set bits are:
   "<<maximum_SameBits(arr, size);
   return 0;
}

ผลลัพธ์

Maximum number of contiguous array elements with same number of set bits are: 3