นับจำนวนสมาชิกติดต่อกันในอาเรย์ที่มีจำนวนบิตเซตเท่ากันใน C++

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

• สมาชิกที่มีจำนวนบิตเซต (set bits) เท่ากัน
• สมาชิกที่มีบิตเซตเท่ากันต้องอยู่ติดต่อกัน (contiguous)

อินพุต

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

เอาต์พุต − Maximum number of contiguous array elements with same number of set bits are − 3

คำอธิบาย − เราจะคำนวณเลขฐานสองของสมาชิกในอาเรย์และนับบิตเซตของแต่ละตัว

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

สมาชิกที่มีจำนวนบิตเซตเท่ากันและอยู่ติดต่อกันคือ 5, 9 และ 12 (มีบิตเซต 2 ตัว) ดังนั้นจำนวนสูงสุดคือ 3

อินพุต − int arr[] = { 5, 8, 1, 2 }

เอาต์พุต − Maximum number of contiguous array elements with same number of set bits are − 2

คำอธิบาย − สมาชิกที่มีบิตเซตเท่ากันและติดต่อกันคือ 1 และ 2 (มีบิตเซต 1 ตัว) ดังนั้นจำนวนสูงสุดคือ 2

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

• รับอินพุตสมาชิกอาเรย์แบบจำนวนเต็ม
• คำนวณขนาดอาเรย์และส่งไปยังฟังก์ชัน
• ใช้ตัวแปรชั่วคราว temp = 1 และ maximum = 1
• สร้าง vector vec เพื่อเก็บจำนวนบิตเซตของแต่ละสมาชิก
• ลูป for จาก 0 ถึงขนาดอาเรย์ คำนวณบิตเซตด้วย __builtin_popcount() และเก็บใน vector
• ลูป for จาก 1 ถึงขนาด vector
• ภายในลูป ตรวจสอบว่า vec[i] == vec[i-1] ให้เพิ่ม temp, มิฉะนั้น reset temp = 1
• อัปเดต maximum = max(maximum, temp)
• คืนค่า maximum
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int maximum_SameBits(int arr[], int size) {
    int temp = 1;
    int maximum = 1;
    vector 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] == vec[i - 1]) {
            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