সমস্যা বিবরণ
0 থেকে N-1 পর্যন্ত Nটি উপাদানের একটি পারমিউটেশন দেওয়া আছে। একটি নির্দিষ্ট বিন্দু (fixed point) হলো এমন একটি ইনডেক্স যেখানে মানটি ইনডেক্সের সমান অর্থাৎ arr[i] = i। আপনাকে সর্বোচ্চ ১টি সোয়াপ করার অনুমতি আছে। আপনি সর্বোচ্চ কতগুলো নির্দিষ্ট বিন্দু পেতে পারেন তা বের করুন।
উদাহরণ
ইনপুট অ্যারে যদি {0, 1, 2, 3, 4, 6, 5} হয়, তবে উত্তর হবে ৭।
- নির্দিষ্ট বিন্দু সমন্বয় করার জন্য ৬ এবং ৫ কে সোয়াপ করতে হবে
- এতে পুরো অ্যারেটিই নির্দিষ্ট বিন্দু হয়ে যায় এবং নির্দিষ্ট বিন্দুর সর্বোচ্চ মান ৭ হয়।
অ্যালগরিদম
- একটি pos অ্যারে তৈরি করুন যা ইনপুট অ্যারেতে প্রতিটি উপাদানের অবস্থান সংরক্ষণ করবে
- এখন অ্যারেটি ট্রাভার্স করুন এবং নিচের কেসগুলো যাচাই করুন −
- যদি a[i] = i হয়। তবে কাউন্ট বাড়িয়ে এগিয়ে যান
- যদি pos[i] = a[i] হয়, অর্থাৎ ২টি পদ সোয়াপ করলে i এবং a[i] উভয়ই নির্দিষ্ট বিন্দু হয়ে যাবে, ফলে কাউন্ট ২ বাড়বে। মনে রাখবেন সোয়াপ সর্বোচ্চ ১বার করা যায়।
- ট্রাভার্সাল শেষে, যদি কোনো সোয়াপ করা না থাকে, অর্থাৎ সোয়াপ করে কাউন্ট ২ বাড়ানো সম্ভব হয়নি, তবে যদি কমপক্ষে ২টি উপাদান নির্দিষ্ট বিন্দু না হয়, তবে ১টি সোয়াপ করে কাউন্ট ১ বাড়ানো যাবে, অর্থাৎ তাদের মধ্যে একটিকে নির্দিষ্ট বিন্দু বানানো যাবে।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int getMaximumFixedPoints(int arr[], int n) { int i, pos[n], count = 0, swapped = 0; for (i = 0; i < n; i++) pos[arr[i]] = i; for (i = 0; i < n; i++) { if (arr[i] == i) { count++; } else if (swapped == 0 && pos[i] == arr[i]) { count += 2; swapped = 1; } } if (swapped == 0 && count < n - 1) { count++; } return count; } int main() { int arr[] = {0, 1, 2, 3, 4, 6, 5}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl; return 0; }আউটপুট
প্রোগ্রামটি কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে −
Maximum edges = 7
