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

ในปัญหานี้ เราได้รับอาร์เรย์ขององค์ประกอบ n และค่าจำนวนเต็ม k หน้าที่ของเราคือค้นหา XOR ขององค์ประกอบทั้งหมดของอาร์เรย์ที่ตั้งค่าบิตเท่ากับ 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> kBitElments;
   for (int i = 0; i < n; i++) {
      if (__builtin_popcount(arr[i]) == k) {
         kBitElments.push_back(arr[i]);
      }
   }
   int result = kBitElments[0];
   for (int i = 1; i < kBitElments.size(); i++)
      result ^= kBitElments[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