資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢與陣列中每個整數進行異或運算時，能得到最小和的數字
概念
對於給定的非負整數陣列 Arr[]，任務是確定一個整數 X，使得 (Arr[0] XOR X) + (Arr[1] XOR X) + … + Arr[n – 1] XOR X 的結果儘可能小。
輸入
Arr[] = {3, 4, 5, 6, 7}輸出
X = 7, Sum = 10
方法
因此，我們將驗證陣列中每個數字在二進位制表示中的第 i 位，並考慮並統計那些第 i 位設定為 '1' 的數字，因為這些設定的位將有助於最大化總和而不是最小化。因此，如果計數大於 N/2，我們必須將此設定的第 i 位構建為 '0'；如果計數小於 N/2，則具有第 i 位設定的數字較少，因此不會影響答案。我們知道根據兩個位上的異或運算，當 A XOR B 且 A 和 B 都相同時，它會產生 '0' 的結果，因此我們將在此數字 (num) 中構建該第 i 位為 '1'，因此 (1 XOR 1) 將給出 '0' 並最小化總和。
示例
// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void findX1(int arr1[], int n1){
int* itr1 = max_element(arr1, arr1 + n1);
int p1 = log2(*itr1) + 1;
int X1 = 0;
for (int i = 0; i < p1; i++) {
int count1 = 0;
for (int j = 0; j < n1; j++) {
if (arr1[j] & (1 << i)) {
count1++;
}
}
if (count1 > (n1 / 2)) {
X1 += 1 << i;
}
}
long long int sum1 = 0;
for (int i = 0; i < n1; i++)
sum1 += (X1 ^ arr1[i]);
cout << "X = " << X1 << ", Sum = " << sum1;
}
// Driver code
int main(){
int arr1[] = { 3, 4, 5, 6, 7 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
findX1(arr1, n1);
return 0;
}輸出
X = 7, Sum = 10
更新於: 2020-07-23
210 次瀏覽
廣告