Trong bài toán này, chúng ta được cung cấp một mảng gồm n phần tử và một giá trị nguyên k. Nhiệm vụ của chúng ta là tìm XOR của tất cả các phần tử của mảng có các bit đặt bằng k.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
array = {2, 12, 44, 103, 17} , K =3 Đầu ra
44
Để giải quyết vấn đề này, chúng ta sẽ đếm bit set của mọi phần tử của mảng và so sánh nó với k. Nếu số bit đặt bằng k, thì chúng ta sẽ đẩy nó thành một vectơ và tìm XOR của tất cả các phần tử của vectơ.
Để tìm số bit đã đặt, chúng tôi sẽ sử dụng __ builtin_popcount () là một hàm tích hợp trong c ++.
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
XOR of all element of the array with 3 set bits is : 44