การหาค่า XOR ของทุกองค์ประกอบในอาร์เรย์ที่มีบิตเซ็ตเท่ากับ K ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ที่มี n องค์ประกอบและค่าจำนวนเต็ม k งานของเราคือการหาค่า XOR ของทุกองค์ประกอบในอาร์เรย์ที่มีจำนวนบิตเซ็ต (set bits) เท่ากับ k

ตัวอย่าง

array = {2, 12, 44, 103, 17} , K = 3

ผลลัพธ์

44

เพื่อแก้ปัญหานี้ เราจะนับจำนวนบิตเซ็ตของแต่ละองค์ประกอบในอาร์เรย์และเปรียบเทียบกับ k หากจำนวนบิตเซ็ตเท่ากับ k เราจะนำองค์ประกอบนั้นใส่ในเวกเตอร์ และหาค่า XOR ของทุกองค์ประกอบในเวกเตอร์นั้น

สำหรับการนับบิตเซ็ต เราจะใช้ฟังก์ชัน __builtin_popcount() ซึ่งเป็นฟังก์ชันสำเร็จรูปใน C++

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

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

int XorKSetBits(int arr[], int n, int k) {
    vector<int> kBitElements;
    for (int i = 0; i < n; i++) {
        if (__builtin_popcount(arr[i]) == k) {
            kBitElements.push_back(arr[i]);
        }
    }
    int result = kBitElements[0];
    for (int i = 1; i < kBitElements.size(); i++)
        result ^= kBitElements[i];
    return result;
}

int main() {
    int arr[] = { 2, 12, 44, 103, 17 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "XOR of all element of the array with " << k << " set bits is : " << XorKSetBits(arr, n, k);
    return 0;
}

ผลลัพธ์

XOR of all element of the array with 3 set bits is : 44