ข้อความโจทย์
เราได้รับอาร์เรย์ n สมาชิก งานคือทำให้ XOR ของอาร์เรย์ทั้งหมดเป็น 0 สามารถทำได้ดังนี้
เลือกสมาชิกใดสมาชิกหนึ่ง −
- หลังเลือกสมาชิกแล้ว สามารถเพิ่มหรือลดค่าลง 1 ได้
- ต้องหาจำนวนการเพิ่ม/ลดขั้นต่ำสำหรับสมาชิกที่เลือก เพื่อให้ XOR ของอาร์เรย์ทั้งหมดเป็นศูนย์
ตัวอย่าง
ถ้า arr[] = {2, 4, 7} ต้องการ 1 การดำเนินการ −
- เลือกสมาชิก 2
- ลดลง 1
- ตอนนี้อาร์เรย์กลายเป็น {3, 4, 7} และ XOR ของมันคือ 0
อัลกอริทึม
- หา XOR ของอาร์เรย์ทั้งหมด
- สมมติเราเลือกสมาชิก arr[i] ต้นทุนที่ต้องใช้สำหรับสมาชิกนั้นจะเป็น absolute(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
