สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบบางอย่าง เราต้องหาองค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์ A แต่ข้อจำกัดคือ เราไม่สามารถใช้ตัวดำเนินการตามเงื่อนไขใดๆ ได้ ดังนั้นหาก A =[12, 63, 32, 24, 78, 56, 20] องค์ประกอบสูงสุดจะเป็น 78
เพื่อแก้ปัญหานี้ เราจะใช้การดำเนินการระดับบิตและ ในตอนแรกเราจะแทรกองค์ประกอบพิเศษหนึ่งรายการ INT_MAX (โดยที่บิตทั้งหมดคือ 1) ในอาร์เรย์ จากนั้นเราจะพยายามหาค่าสูงสุดและค่าของคู่ใด ๆ จากอาร์เรย์ ค่าสูงสุดที่ได้รับนี้จะมีค่า AND ของ INT_MAX และองค์ประกอบที่ใหญ่ที่สุดของอาร์เรย์ดั้งเดิม และนี่จะเป็นผลลัพธ์
ตัวอย่าง
#include <iostream>
#include <vector>
using namespace std;
int checkBit(int pattern, vector<int> arr, int n) {
int count = 0;
for (int i = 0; i < n; i++)
if ((pattern & arr[i]) == pattern)
count++;
return count;
}
int findLargestElement(int arr[], int n) {
vector<int> elements_vector(arr, arr + n);
elements_vector.push_back(INT_MAX);
n++;
int res = 0;
for (int bit = 31; bit >= 0; bit--) {
int count = checkBit(res | (1 << bit), elements_vector, n);
if ((count | 1) != 1)
res |= (1 << bit);
}
return res;
}
int main() {
int arr[] = {12, 63, 32, 24, 78, 56, 20};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Largest element is: " << findLargestElement(arr, n);
} ผลลัพธ์
Largest element is: 78
