আমাদেরকে একটি ধনাত্মক পূর্ণসংখ্যা টাইপ অ্যারে দেওয়া হয়েছে, ধরা যাক, যে কোনও প্রদত্ত আকারের arr[] যাতে একটি অ্যারের উপাদানগুলির মান 0 এর চেয়ে বেশি তবে একটি অ্যারের আকারের চেয়ে কম হওয়া উচিত। কাজটি হল অ্যারেকে এমনভাবে সাজানো যাতে arr[i] শুধুমাত্র প্রদত্ত O(1) স্পেসের মধ্যে arr[arr[i]] হয়ে যায় এবং চূড়ান্ত ফলাফল প্রিন্ট করে।
আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -
ইনপুট − int arr[] ={0 3 2 1 5 4 }
আউটপুট − বিন্যাসের পূর্বে বিন্যাস:0 3 2 1 5 4 একটি বিন্যাসের পুনর্বিন্যাস যাতে arr[i] হয়ে যায় arr[arr[i]] সঙ্গে O(1) অতিরিক্ত স্থান হল:0 1 2 3 4 5
ব্যাখ্যা − আমাদেরকে 6 আকারের একটি পূর্ণসংখ্যার অ্যারে দেওয়া হয়েছে এবং একটি অ্যারের মানের সমস্ত উপাদান 6-এর কম। এখন, আমরা অ্যারেটিকে পুনর্বিন্যাস করব অর্থাৎ arr[arr[0] is 0, arr[arr[1]] হল 1, arr [arr[2]] হল 2, arr[arr[3]] হল 3, arr[arr[4]] হল 4 এবং arr[arr[5]] হল 5৷ সুতরাং, পুনর্বিন্যাস করার পর চূড়ান্ত অ্যারে হল 0 1 2 ৩ ৪ ৫।
ইনপুট − int arr[] ={1, 0}
আউটপুট − বিন্যাসের পূর্বে বিন্যাস:1 0একটি বিন্যাসের পুনর্বিন্যাস যাতে arr[i] arr[arr[i]] হয়ে যায় O(1) অতিরিক্ত স্থান হল:0 1
ব্যাখ্যা − আমাদেরকে 2 আকারের একটি পূর্ণসংখ্যার অ্যারে দেওয়া হয়েছে এবং একটি অ্যারের মানের সমস্ত উপাদান 2-এর চেয়ে কম। এখন, আমরা অ্যারেটিকে পুনর্বিন্যাস করব অর্থাৎ arr[arr[0] হল 1 এবং arr[arr[1]] হল 0। তাই , পুনর্বিন্যাস করার পরে চূড়ান্ত অ্যারে হল 0 1।
ইনপুট − int arr[] ={1, 0, 2, 3}
আউটপুট − বিন্যাসের আগে অ্যারে:1 0 2 3একটি অ্যারের পুনর্বিন্যাস যাতে arr[i] হয়ে যায় arr[arr[i]] এর সাথে O(1) অতিরিক্ত স্থান হল:0 1 2 3
ব্যাখ্যা − আমাদেরকে 4 আকারের একটি পূর্ণসংখ্যার অ্যারে দেওয়া হয়েছে এবং একটি অ্যারের মানের সমস্ত উপাদান 4-এর চেয়ে কম। এখন, আমরা অ্যারেটিকে পুনর্বিন্যাস করব অর্থাৎ arr[arr[0] is 0, arr[arr[1]] হল 1, arr [arr[2]] হল 2 এবং arr[arr[3]] হল 3৷ সুতরাং, পুনর্বিন্যাস করার পর চূড়ান্ত অ্যারে হল 0 1 2 3৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
পূর্ণসংখ্যা ধরণের উপাদানগুলির একটি অ্যারে ইনপুট করুন এবং একটি অ্যারের আকার গণনা করুন
-
বিন্যাস করার আগে অ্যারেটি প্রিন্ট করুন এবং ফাংশনটিকে পুনর্বিন্যাস (arr, size)
কল করুন -
ফাংশনের ভিতরে পুনঃবিন্যাস(arr, size)
-
i থেকে 0 পর্যন্ত FOR লুপ শুরু করুন যতক্ষণ না আমি আকারের চেয়ে কম। লুপের ভিতরে, temp সেট করুন arr[arr[i]] % সাইজ এবং arr[i] +=temp * সাইজ।
-
i থেকে 0 পর্যন্ত 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(){
//input an array
int arr[] = {0, 3, 2, 1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
//print the original Array
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//calling the function to rearrange the array
Rearrangement(arr, size);
//print the array after rearranging the values
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
