আমাদের একটি ধনাত্মক পূর্ণসংখ্যা টাইপের অ্যারে দেওয়া আছে, ধরুন arr[] যেকোনো দেওয়া আকারের যাতে অ্যারেতে উপাদানগুলির মান ০-এর চেয়ে বড় কিন্তু অ্যারের আকারের চেয়ে ছোট। কাজটি হল অ্যারেটিকে এমনভাবে পুনর্বিন্যাস করা যাতে arr[i] হয়ে যায় arr[arr[i]] দেওয়া O(1) স্পেসের মধ্যে এবং চূড়ান্ত ফলাফলটি প্রিন্ট করা হবে।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইনপুট - 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
ব্যাখ্যা - আমাদের আকার ৬-এর একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে এবং অ্যারেতে সকল উপাদানের মান ৬-এর চেয়ে কম। এখন আমরা অ্যারেটিকে পুনর্বিন্যাস করব: 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
ব্যাখ্যা - আমাদের আকার ২-এর একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে এবং অ্যারেতে সকল উপাদানের মান ২-এর চেয়ে কম। এখন আমরা অ্যারেটিকে পুনর্বিন্যাস করব: 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
ব্যাখ্যা - আমাদের আকার ৪-এর একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে এবং অ্যারেতে সকল উপাদানের মান ৪-এর চেয়ে কম। এখন আমরা অ্যারেটিকে পুনর্বিন্যাস করব: 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 = ০ থেকে size পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে temp = arr[arr[i]] % size এবং arr[i] += temp * size সেট করুন।
- i = ০ থেকে size পর্যন্ত একটি FOR লুপ শুরু করুন। লুপের ভিতরে 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
