C++を使用して配列を適切にするために削除する必要のある要素の最小数。

問題の説明

配列「arr」が与えられた場合、タスクは、配列を適切にするために削除する要素の最小数を見つけることです。

シーケンスa1、a2、a3。 。 .anは、各要素a [i]に対して、a [i] + a [j]が2の累乗であるような要素a[j]（iはjと等しくない）が存在する場合に適切と呼ばれます。

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