সমস্যা বিবৃতি
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 থাকে তাহলে আমরা উত্তরে 1 যোগ করব কারণ 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