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을 추가합니다.

예시

#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