Đề bài
Cho mảng số nguyên không âm và số nguyên k, tìm tập con có độ dài lớn nhất sao cho OR bitwise của các phần tử bằng k.
Ví dụ
Input: array = [1, 4, 2], k = 3 Output: [1, 2] OR bitwise của 1 và 2 bằng 3. Không thể có tập con dài hơn 2.
Thuật toán
Các tính chất của OR bitwise:
0 OR 0 = 0 1 OR 0 = 1 1 OR 1 = 1
- Với mọi vị trí bit = 0 trong k, vị trí tương ứng trong tất cả phần tử tập con kết quả phải là 0.
- Với vị trí bit = 1 trong k, phải có ít nhất một phần tử có bit 1 tại vị trí đó. Các phần tử khác có 0 hoặc 1 không quan trọng.
- Do đó, duyệt mảng ban đầu. Khi quyết định phần tử có vào tập con hay không, kiểm tra xem có vị trí nào bit k = 0 mà bit phần tử = 1 không. Nếu có, bỏ qua phần tử đó, ngược lại thêm vào tập con.
- Cách kiểm tra: OR bitwise của k và phần tử. Nếu không bằng k, tồn tại vị trí đó -> bỏ qua. Nếu bằng k, thêm vào tập con.
- Bước cuối: kiểm tra xem có ít nhất một phần tử có bit 1 tại vị trí bit 1 của k. Tính OR của tập con kết quả. Nếu bằng k, đó là đáp án. Ngược lại không tồn tại tập con thỏa mãn.
Ví dụ
#include <bits/stdc++.h> using namespace std; void getSubSet(int *arr, int n, int k){ vector<int> v; for (int i = 0; i < n; i++) { if ((arr[i] | k) == k) v.push_back(arr[i]); } int ans = 0; for (int i = 0; i < v.size(); i++) { ans |= v[i]; } if (ans != k) { cout << "Tập con không tồn tại" << endl; return; } cout << "Kết quả = "; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } int main(){ int arr[] = { 1, 4, 2 }; int k = 3; int n = sizeof(arr) / sizeof(arr[0]); getSubSet(arr, n, k); return 0; }Kết quả
Kết quả = 1 2