C++で配列を「良い配列」にするために削除が必要な最小要素数を求めるアルゴリズム

問題の概要

整数型配列「arr」が与えられたとき、この配列を「良い配列」にするために削除する必要がある要素の最小数を求めるのが課題です。

ここで「良い配列」とは、数列 a1, a2, a3, ... an の各要素 a[i] に対して、i ≠ j を満たす別の要素 a[j] が必ず存在し、a[i] + a[j] の和が2の累乗(べき乗)になるような配列のことを指します。

具体例

arr1[] = {1, 1, 7, 1, 5}

上記の配列では、要素「5」を1つ削除するだけで配列は良い配列になります。削除後は、任意のペア arr[i] + arr[j] の和が2の累乗になります。

• arr[0] + arr[1] = (1 + 1) = 2 → 2の累乗
• arr[0] + arr[2] = (1 + 7) = 8 → 2の累乗

このように、ペアを形成できない要素だけを取り除けばよいことがポイントです。

アルゴリズムの考え方

1. 削除が必要なのは、「a[i] + a[j] が2の累乗となるような a[j] が配列内に存在しない」要素 a[i] のみです。
2. map(連想配列)を使って、配列内の各値の出現回数を記録します。
3. 各要素 a[i] について、2の累乗(2^0 〜 2^30)との差「(2の累乗) − a[i]」が配列内に存在するかを確認し、ペアが存在するかどうかを判定します。

ペアの判定では、同じ値同士でペアになるケース(例：1 + 1 = 2)も考慮する必要があります。そのため、ペア候補の値の出現回数が2以上、または値が異なる要素である場合にのみ、ペアが存在するとみなします。

C++での実装例

#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;
}

コードの解説

まず、map を使って各要素の出現回数を数えます。その後、各要素 a[i] に対して j を 0 から 30 までループし、「2^j − a[i]」が配列内に存在するかどうかを調べます。存在する場合はその要素は削除不要(doNotRemove = true)となり、存在しない場合は削除カウントを1つ増やします。

このアルゴリズムの計算量は、要素ごとに最大31回の探索を行うため、O(n × 31)、すなわち実質 O(n) で非常に効率的です。

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum elements to be deleted = 1

この例では、要素「1」と「7」は互いにペア(1+1=2、1+7=8)を形成できますが、「5」だけはどの要素と組み合わせても2の累乗にならないため、削除が必要な要素は1個となります。