সমস্যা বিবরণ
n সংখ্যক ইন্টিজারের একটি সেট দেওয়া আছে। মিনিমাম সংখ্যক অপারেশন (সেটে এলিমেন্ট ইনসার্ট/ডিলিট করা) করুন যাতে সেটের MEX x হয়ে যায় (যে মান দেওয়া আছে)।
নোট − একটি ইন্টিজার সেটের MEX হলো সেই সেটে নাও থাকা ন্যূনতম নন-নেগেটিভ ইন্টিজার। উদাহরণস্বরূপ, সেট {0, 2, 4} এর MEX হলো ১ এবং সেট {1, 2, 3} এর MEX হলো ০।
উদাহরণ
যদি n = 5, x = 3 এবং অ্যারে = {0, 4, 5, 6, 7} হয়, তবে মিনিমাম ২ অপারেশন দরকার।
অ্যালগরিদম
- অ্যাপ্রোচটি হলো ফাইনাল সেটে x-এর চেয়ে ছোট সব এলিমেন্ট থাকতে হবে, x থাকতে পারবে না এবং x-এর চেয়ে বড় এলিমেন্টগুলো কনসিডার করা হবে না।
- সেজন্য, x-এর চেয়ে ছোট যেসব এলিমেন্ট ইনিশিয়াল সেটে নেই, তাদের কাউন্ট করুন এবং আন্সারে যোগ করুন।
- যদি x থাকা থাকে, তবে ১ যোগ করুন কারণ x রিমুভ করতে হবে।
উদাহরণ
#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
