हमें एक धनात्मक पूर्णांक प्रकार की सरणी दी गई है, मान लीजिए arr[] किसी भी दिए गए आकार की, जिसमें सरणी के तत्वों का मान 0 से अधिक लेकिन सरणी के आकार से कम होना चाहिए। कार्य सरणी को इस तरह पुनर्व्यवस्थित करना है कि arr[i] दिए गए O(1) स्थान में arr[arr[i]] बन जाए और अंतिम परिणाम प्रिंट करें।
विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:
इनपुट: int arr[] = {0, 3, 2, 1, 5, 4}
आउटपुट: व्यवस्था से पहले सरणी: 0 3 2 1 5 4 O(1) अतिरिक्त स्थान के साथ arr[i] arr[arr[i]] बन जाए ऐसा सरणी का पुनर्व्यवस्थित रूप: 0 1 2 3 4 5
व्याख्या: हमें आकार 6 की एक पूर्णांक सरणी दी गई है और सरणी के सभी तत्वों का मान 6 से कम है। अब, हम सरणी को पुनर्व्यवस्थित करेंगे: arr[arr[0]] 0 है, arr[arr[1]] 1 है, arr[arr[2]] 2 है, arr[arr[3]] 3 है, arr[arr[4]] 4 है और arr[arr[5]] 5 है। इसलिए, पुनर्व्यवस्था के बाद अंतिम सरणी 0 1 2 3 4 5 है।
इनपुट: int arr[] = {1, 0}
आउटपुट: व्यवस्था से पहले सरणी: 1 0 O(1) अतिरिक्त स्थान के साथ arr[i] arr[arr[i]] बन जाए ऐसा सरणी का पुनर्व्यवस्थित रूप: 0 1
व्याख्या: हमें आकार 2 की एक पूर्णांक सरणी दी गई है और सरणी के सभी तत्वों का मान 2 से कम है। अब, हम सरणी को पुनर्व्यवस्थित करेंगे: arr[arr[0]] 1 है और arr[arr[1]] 0 है। इसलिए, पुनर्व्यवस्था के बाद अंतिम सरणी 0 1 है।
इनपुट: int arr[] = {1, 0, 2, 3}
आउटपुट: व्यवस्था से पहले सरणी: 1 0 2 3 O(1) अतिरिक्त स्थान के साथ arr[i] arr[arr[i]] बन जाए ऐसा सरणी का पुनर्व्यवस्थित रूप: 0 1 2 3
व्याख्या: हमें आकार 4 की एक पूर्णांक सरणी दी गई है और सरणी के सभी तत्वों का मान 4 से कम है। अब, हम सरणी को पुनर्व्यवस्थित करेंगे: arr[arr[0]] 0 है, arr[arr[1]] 1 है, arr[arr[2]] 2 है और arr[arr[3]] 3 है। इसलिए, पुनर्व्यवस्था के बाद अंतिम सरणी 0 1 2 3 है।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:
- पूर्णांक प्रकार के तत्वों की एक सरणी इनपुट करें और सरणी का आकार गणना करें।
- व्यवस्था से पहले सरणी प्रिंट करें और फंक्शन Rearrangement(arr, size) को कॉल करें।
- फंक्शन Rearrangement(arr, size) के अंदर:
- i को 0 से size से कम तक लूप चलाएं। अंदर, temp को arr[arr[i]] % size पर सेट करें और arr[i] += temp * size।
- i को 0 से size से कम तक लूप चलाएं। अंदर, arr[i] = arr[i] / size सेट करें।
- परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size) {
for(int i = 0; i < size; i++) {
int temp = arr[arr[i]] % size;
arr[i] += temp * size;
}
for(int i = 0; i < size; i++) {
arr[i] = arr[i] / size;
}
}
int main() {
// एक सरणी इनपुट करें
int arr[] = {0, 3, 2, 1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
// मूल सरणी प्रिंट करें
cout << "Array before Arrangement: ";
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
// सरणी को पुनर्व्यवस्थित करने के लिए फंक्शन कॉल करें
Rearrangement(arr, size);
// मानों को पुनर्व्यवस्थित करने के बाद सरणी प्रिंट करें
cout << "\nRearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
for(int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
return 0;
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Array before Arrangement: 0 3 2 1 5 4 Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5