সমস্যা বিবৃতি
0 থেকে N-1 পর্যন্ত N উপাদানগুলির একটি স্থানান্তর দেওয়া হয়েছে। একটি স্থির বিন্দু হল একটি সূচক যেখানে মানটি সূচকের সমান যেমন arr[i] =i। আপনি সর্বোচ্চ 1টি অদলবদল করতে পারবেন। আপনি পেতে পারেন এমন সর্বোচ্চ সংখ্যক নির্দিষ্ট পয়েন্ট খুঁজুন।
উদাহরণ
যদি ইনপুট অ্যারে হয় {0, 1, 2, 3, 4, 6, 5} তাহলে উত্তর হল 7৷
- স্থির বিন্দু সামঞ্জস্য করতে, আমাদের 6 এবং 5 অদলবদল করতে হবে
- এর পরে সম্পূর্ণ অ্যারে ফিক্সড পয়েন্ট হয়ে যায় এবং ফিক্সড পয়েন্টের সর্বোচ্চ মান 7 হয়।
অ্যালগরিদম
- একটি অ্যারে পোস তৈরি করুন যা ইনপুট অ্যারেতে প্রতিটি উপাদানের অবস্থান রাখে
- এখন, আমরা অ্যারেটি ট্র্যাভার্স করি এবং নিম্নলিখিত ক্ষেত্রে রয়েছে −
- যদি, a[i] =i. আমরা কেবল গণনা বৃদ্ধি করতে পারি এবং এগিয়ে যেতে পারি
- যদি, pos[i] =a[i] যার মানে হল 2টি পদ অদলবদল করলে i এবং a[i] স্থির বিন্দু হবে, তাই গণনা 2 দ্বারা বৃদ্ধি পাবে। মনে রাখবেন যে অদলবদল সর্বাধিক একবার করা যেতে পারে .
- ট্র্যাভার্সালের শেষে, যদি আমরা কোনো অদলবদল না করে থাকি, তাহলে এর মানে হল যে আমাদের সোয়াপ 2 দ্বারা গণনা বাড়াতে সক্ষম হয়নি, তাই এখন যদি অন্তত 2টি উপাদান থাকে যা নির্দিষ্ট বিন্দু নয়, আমরা করতে পারি গণনা 1 দ্বারা বৃদ্ধি করার জন্য একটি অদলবদল করুন, অর্থাৎ এই পয়েন্টগুলির একটিকে একটি নির্দিষ্ট বিন্দুতে পরিণত করুন৷
উদাহরণ
#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
