คำชี้แจงปัญหา
เราได้รับอาร์เรย์ขององค์ประกอบ n ภารกิจคือทำให้ XOR ของทั้งอาร์เรย์ 0 เราสามารถทำตามเพื่อให้บรรลุนี้
เราสามารถเลือกองค์ประกอบใดก็ได้ -
- หลังจากเลือกองค์ประกอบแล้ว เราสามารถเพิ่มขึ้นหรือลดลงได้ 1
- เราจำเป็นต้องค้นหาจำนวนขั้นต่ำของการดำเนินการเพิ่ม/ลดที่จำเป็นสำหรับองค์ประกอบที่เลือกเพื่อให้ผลรวม XOR ของอาร์เรย์ทั้งหมดเป็นศูนย์
ตัวอย่าง
ถ้า arr[] ={2, 4, 7} จำเป็นต้องมีการดำเนินการ 1 ครั้ง −
- เลือกองค์ประกอบ 2
- ลดทีละ 1
- ตอนนี้อาร์เรย์กลายเป็น {3, 4, 7} และ XOR ของมันคือ 0
อัลกอริทึม
- ค้นหา XOR ของทั้งอาร์เรย์
- ตอนนี้ สมมติว่าเราได้เลือกองค์ประกอบ arr[i] ดังนั้นค่าใช้จ่ายที่จำเป็นสำหรับองค์ประกอบนั้นจะเป็นแบบสัมบูรณ์(arr[i]-(XORsum^arr[i]))
- การคำนวณค่าสัมบูรณ์ขั้นต่ำสำหรับแต่ละองค์ประกอบจะเป็นการดำเนินการขั้นต่ำที่เรากำหนด
ตัวอย่าง
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getMinCost(int *arr, int n) {
int operations = INT_MAX;
int elem;
int xorValue = 0;
for (int i = 0; i < n; ++i) {
xorValue = xorValue ^ arr[i];
}
for (int i = 0; i < n; ++i) {
if (operations > abs((xorValue ^ arr[i]) - arr[i])) {
operations = abs((xorValue ^ arr[i]) - arr[i]);
elem = arr[i];
}
}
cout << "Element= " << elem << endl;
cout << "Minimum required operations = " << abs(operations) << endl;
}
int main() {
int arr[] = {2, 4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
getMinCost(arr, n);
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้:
Element = 2 Minimum required operations = 1
