এই নিবন্ধে, আমরা একটি প্রদত্ত অ্যারেকে k-এলিমেন্ট দ্বারা ডানদিকে ঘোরানোর জন্য বিপরীত অ্যালগরিদম বুঝতে পারব, উদাহরণস্বরূপ −
Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
Output : { 43, 7, 3, 7, 4, 6, 2, 6 }
Explanation : Rotating each element of array by 4-element to the right gives { 43, 7, 3, 7, 4, 6, 2, 6 }.
Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
Output : { 4, 9, 3, 8, 5, 8, 2, 1 } সমাধান খোঁজার পদ্ধতি
আপনি প্রতিটি উপাদানকে ডানদিকে স্থানান্তর করে এবং এই পদ্ধতিটি কে-বার পুনরাবৃত্তি করে সহজেই এই সমস্যার সমাধান করতে পারেন। তবে এটি আরও সময় নেবে কারণ এর সময় জটিলতা হবে O(k * N).
রিভার্সাল অ্যালগরিদম:রিভার্সাল একটি অ্যারেকে রিভার্স করে এবং কিছু উপাদান রেঞ্জকে বিপরীত করে অ্যারে ঘোরানো যায়। এই অ্যালগরিদম অনুযায়ী -
- প্রথমে, পুরো অ্যারেটি বিপরীত করুন।
- k-এর মডুলাস N(অ্যারে সাইজ) দিয়ে k-এর পরিবর্তন করুন কারণ k হল N-এর থেকে বড়।
- ক্রমানুসারে পেতে অ্যারের প্রথম k উপাদানগুলিকে বিপরীত করুন।
- অতঃপর অবশিষ্ট উপাদানগুলির পরিসরকে বিপরীত করুন, যেমন, k থেকে N-1 পর্যন্ত।
উদাহরণ
using namespace std;
#include <bits/stdc++.h>
void reverse(int nums[], int start,int end) {
int temp=0;
// reversing array with swapping start element with end element.
while(start<=end){
temp=nums[end];
nums[end]=nums[start];
nums[start]=temp;
start++;
end--;
}
}
int main() {
int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 };
int N = sizeof(arr)/sizeof(arr[0]);
int k = 4;
// reversing whole array
reverse(arr, 0, N-1);
k = k%N;
// reversing element range of 0 to k-1.
reverse(arr, 0, k-1);
// reversing element range of k to last element.
reverse(arr, k, N-1);
cout << "Array after rotating by k-elements : ";
for(int i = 0;i<N;i++)
cout << arr[i] << " ";
return 0;
} আউটপুট
Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
উপসংহার
এই প্রবন্ধে আমরা রিভার্সাল অ্যালগরিদম ব্যবহার করে কে-এলিমেন্টগুলির দ্বারা অ্যারের ডান ঘূর্ণনের সমস্যা নিয়ে আলোচনা করেছি৷ আমরা আলোচনা করেছি রিভার্সাল অ্যালগরিদম কী এবং এই সমস্যার সমাধানের জন্য কীভাবে এটি প্রয়োগ করা যেতে পারে৷ আমরা এই সমস্যা সমাধানের জন্য C++ কোড নিয়েও আলোচনা করেছি। আমরা এই কোডটি অন্য যেকোনো ভাষায় লিখতে পারি যেমন C, Java, Python, ইত্যাদি। আশা করি আপনার এই নিবন্ধটি সহায়ক হবে।
