Đề bài
Cho mảng n phần tử. Nhiệm vụ là làm cho XOR của toàn bộ mảng bằng 0. Chúng ta có thể làm theo cách sau.
Chọn bất kỳ phần tử nào −
- Sau khi chọn phần tử, có thể tăng hoặc giảm nó đi 1.
- Cần tìm số phép tăng/giảm tối thiểu cho phần tử được chọn để tổng XOR của toàn bộ mảng bằng 0.
Ví dụ
Nếu arr[] = {2, 4, 7} thì cần 1 phép toán −
- Chọn phần tử 2
- Giảm nó đi 1
- Mảng trở thành {3, 4, 7} và XOR của nó là 0
Thuật toán
- Tìm XOR của toàn bộ mảng
- Giả sử chọn phần tử arr[i], chi phí cho phần tử đó sẽ là abs(arr[i] - (XORsum ^ arr[i]))
- Tính giá trị tuyệt đối nhỏ nhất cho mỗi phần tử sẽ là số phép toán tối thiểu yêu cầu
Ví dụ
#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 << "Phần tử = " << elem << endl;
cout << "Số phép toán tối thiểu = " << abs(operations) << endl;
}
int main() {
int arr[] = {2, 4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
getMinCost(arr, n);
return 0;
}
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Phần tử = 2 Số phép toán tối thiểu = 1