指定されたセットのMEXをC++で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を追加します。

例

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

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum required operations = 2