Tuyên bố vấn đề
Cho một tập hợp n số nguyên, hãy thực hiện số phép toán tối thiểu (bạn có thể chèn / xóa các phần tử vào / khỏi tập hợp) để làm cho MEX của tập hợp bằng x (đã cho).
Lưu ý - MEX của một tập hợp các số nguyên là số nguyên không âm tối thiểu không tồn tại trong tập hợp đó. Ví dụ:MEX của tập hợp {0, 2, 4} là 1 và MEX của tập hợp {1, 2, 3} là 0
Ví dụ
Nếu n =5 và x =3 và mảng là {0, 4, 5, 6, 7} thì chúng ta yêu cầu tối thiểu 2 phép toán
Thuật toán
- Cách tiếp cận là để thấy rằng trong tập hợp cuối cùng, tất cả các phần tử nhỏ hơn x sẽ tồn tại, x không nên tồn tại và bất kỳ phần tử nào lớn hơn x không quan trọng.
- Vì vậy, chúng tôi sẽ đếm số phần tử nhỏ hơn x không tồn tại trong tập hợp ban đầu và thêm phần tử này vào câu trả lời.
- Nếu x tồn tại, chúng tôi sẽ thêm 1 vào câu trả lời vì x cần được xóa.
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Minimum required operations = 2