Tuyên bố vấn đề
Chúng ta được cho một mảng gồm n phần tử. Nhiệm vụ là tạo XOR cho toàn bộ mảng 0. Chúng ta có thể làm như sau để đạt được điều này.
Chúng tôi có thể chọn bất kỳ một phần tử nào -
- Sau khi chọn phần tử, chúng tôi có thể tăng hoặc giảm phần tử đó đi 1.
- Chúng tôi cần tìm số lượng tối thiểu của hoạt động tăng / giảm cần thiết cho phần tử đã chọn để làm cho tổng XOR của toàn bộ mảng bằng không
Ví dụ
Nếu arr [] ={2, 4, 7} thì 1 thao tác là bắt buộc -
- Chọn phần tử 2
- Giảm nó đi 1
- Bây giờ 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
- Bây giờ, giả sử chúng ta đã chọn phần tử arr [i], vì vậy chi phí cần thiết cho phần tử đó sẽ là tuyệt đối (arr [i] - (XORsum ^ arr [i]))
- Tính toán tối thiểu các giá trị tuyệt đối này cho từng phần tử sẽ là thao tác bắt buộc tối thiểu của chúng tôi
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 << "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;
} Đầu ra
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:
Element = 2 Minimum required operations = 1