समस्या कथन
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