資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中使陣列異或結果為零的最小運算元
問題陳述
給定一個包含n個元素的陣列。任務是使整個陣列的異或結果為0。我們可以執行以下操作來實現這一點。
我們可以選擇任何一個元素 -
- 選擇元素後，我們可以將其加1或減1。
- 我們需要找到使整個陣列的異或和為零所需的最少增量/減量操作次數。
示例
如果arr[] = {2, 4, 7}，則需要1次操作 -
- 選擇元素2
- 將其減1
- 現在陣列變為{3, 4, 7}，其異或結果為0
演算法
- 找到整個陣列的異或結果
- 現在，假設我們選擇了元素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
更新於：2019年11月22日
426 次瀏覽
廣告