समस्या कथन
0 से N-1 तक के N तत्वों का एक क्रमपरिवर्तन दिया गया है। एक निश्चित बिंदु वह इंडेक्स है जिस पर मान इंडेक्स के समान होता है यानी arr[i] = i। आपको अधिकतम 1 स्वैप करने की अनुमति है। अधिकतम निश्चित बिंदुओं की संख्या ढूंढें जो आप प्राप्त कर सकते हैं।
उदाहरण
यदि इनपुट ऐरे है {0, 1, 2, 3, 4, 6, 5} तो उत्तर 7 है।
- निश्चित बिंदु को समायोजित करने के लिए, हमें 6 और 5 को स्वैप करना होगा
- इसके बाद पूरा ऐरे निश्चित बिंदु बन जाता है और निश्चित बिंदु का अधिकतम मान 7 होता है।
एल्गोरिदम
- एक ऐरे pos बनाएं जो इनपुट ऐरे में प्रत्येक तत्व की स्थिति को ट्रैक करे
- अब, हम ऐरे को ट्रैवर्स करते हैं और निम्न मामले होते हैं -
- यदि, 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