C++에서 배열의 XOR을 0으로 만드는 최소 작업

문제 설명

n개의 요소로 구성된 배열이 제공됩니다. 작업은 전체 배열의 XOR을 0으로 만드는 것입니다. 이를 달성하기 위해 다음을 수행할 수 있습니다.

요소 중 하나를 선택할 수 있습니다 -

• 요소를 선택한 후 1씩 증가 또는 감소할 수 있습니다.
• 전체 배열의 XOR 합을 0으로 만들기 위해 선택한 요소에 필요한 최소 증가/감소 연산 수를 찾아야 합니다.

예시

arr[] ={2, 4, 7}이면 1개의 연산이 필요합니다 -

• 요소 2 선택
• 1씩 감소
• 이제 배열은 {3, 4, 7}이 되고 XOR은 0입니다.

알고리즘

• 전체 배열의 XOR 찾기
• 이제 요소를 선택했다고 가정합니다. 따라서 해당 요소에 필요한 비용은 절대(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