C++で集合のMEXをxに一致させるための最小操作回数を求める方法

問題文

n個の整数からなる集合が与えられます。要素の挿入・削除を最小回数の操作で行い、集合のMEXを指定された値xに一致させてください。

注: 整数の集合におけるMEXとは、その集合に含まれていない最小の非負整数のことです。例えば、集合 {0, 2, 4} のMEXは 1、集合 {1, 2, 3} のMEXは 0 となります。

入出力例

n = 5、x = 3、配列が {0, 4, 5, 6, 7} の場合、必要な最小操作回数は 2 回です。

アルゴリズム

• 最終的な集合では、「x 未満の要素がすべて存在すること」「x 自体は存在しないこと」が求められ、x より大きい要素はいくつあっても構いません。この性質に着目するのがポイントです。
• そこで、初期集合に存在しない x 未満の要素の個数を数え、その数を答えに加算します。これらは挿入操作が必要な要素です。
• さらに、x が集合に存在する場合は、x を削除する必要があるため、答えに 1 を加算します。

実装例(C++)

#include <iostream>
using namespace std;
int getMinOperations(int *arr, int n, int x) {
    int k = x, i = 0;
    while (n--) {
        if (arr[n] < x) {
            --k;
        }
        if (arr[n] == x) {
            ++k;
        }
    }
    return k;
}
int main() {
    int arr[] = {0, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]); int x = 3;
    cout << "Minimum required operations = " << getMinOperations(arr, n, x) << endl;
    return 0;
}

コードの解説

変数 k は最終的な操作回数を表します。初期値を x とすることで、「0 から x-1 までの x 個の要素をすべて挿入しなければならない」という状況を表現しています。配列を走査しながら、x 未満の要素が見つかるたびに k をデクリメントし(必要な挿入が 1 つ減る)、x と等しい要素が見つかるたびに k をインクリメントします(削除操作が 1 回必要)。計算量は O(n) と非常に効率的です。

出力

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

Minimum required operations = 2