问题陈述
给定数组“arr”，任务是找到要删除的最小数量的元素以使数组良好。
序列a1，a2，a3。。如果对于每个元素a[i]，都存在一个元素a[j]（i不等于j），使得a[i]+a[j]为2的幂，则.an被称为良好。
arr1[] = {1, 1, 7, 1, 5}
在上面的数组中，如果我们删除元素“5”，那么数组将变为好数组。在此之后，任何一对arr[i]+arr[j]都是2的幂-
arr[0]+arr[1]=（1+1）=22的幂
arr[0]+arr[2]=（1+7）=8这是2的幂
算法
1. We have to delete only such a[i] for which there is no a[j] such that a[i] + a[i] is a power of 2.
2. For each value find the number of its occurrences in the array
3. Check that a[i] doesn’t have a pair a[j]
示例
#include <iostream>
#include <map>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minDeleteRequred(int *arr, int n){
map<int, int> frequency;
for (int i = 0; i < n; ++i) {
frequency[arr[i]]++;
}
int delCnt = 0;
for (int i = 0; i < n; ++i) {
bool doNotRemove = false;
for (int j = 0; j < 31; ++j) {
int pair = (1 << j) - arr[i];
if (frequency.count(pair) &&
(frequency[pair] > 1 ||
(frequency[pair] == 1 &&
pair != arr[i]))) {
doNotRemove = true;
break;
}
}
if (!doNotRemove) {
++delCnt;
}
}
return delCnt;
}
int main(){
int arr[] = {1, 1, 7, 1, 5};
cout << "Minimum elements to be deleted = " << minDeleteRequred(arr, SIZE(arr)) << endl;
return 0;
}
输出结果
当您编译并执行上述程序时。它产生以下输出-
Minimum elements to be deleted = 1
