数据结构
网络
关系数据库管理系统 (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 次浏览
广告