为了使用C ++使数组良好，应删除的最小元素数。

问题陈述

给定数组“ 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）= 2 2的幂

• 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