এই আর্টিকেলে, আমরা রিভার্সাল অ্যালগরিদম বুঝব যেটি দিয়ে একটি অ্যারে k-এলিমেন্ট ডানে রোটেট করা যায়, উদাহরণস্বরূপ −
ইনপুট : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
আউটপুট : { 43, 7, 3, 7, 4, 6, 2, 6 }
ব্যাখ্যা : অ্যারেতার প্রতিটি উপাদান ৪-এলিমেন্ট ডানে রোটেট করলে { 43, 7, 3, 7, 4, 6, 2, 6 } পাওয়া যায়।
ইনপুট : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
আউটপুট : { 4, 9, 3, 8, 5, 8, 2, 1 }
সমাধানের পদ্ধতি
আপনি সহজে এই সমস্যা সমাধান করতে পারেন প্রতিটি উপাদান ডানে শিফট করে এবং এই প্রসেস k-বার রিপিট করে। কিন্তু এতে বেশি সময় লাগবে কারণ এর টাইম কমপ্লেক্সিটি O(k * N) হবে।
রিভার্সাল অ্যালগরিদম: রিভার্সাল মানে একটি অ্যারে রিভার্স করা, এবং অ্যারে রোটেট করা যাবে কিছু এলিমেন্ট রেঞ্জ রিভার্স করে। এই অ্যালগরিদম অনুযায়ী −
- প্রথমে, পুরো অ্যারেটি রিভার্স করুন।
- k কে N (অ্যারে সাইজ) দিয়ে মডুলাস দিয়ে মডিফাই করুন কারণ k, N-র চেয়ে বড় হতে পারে।
- অ্যারেতার প্রথম k এলিমেন্ট রিভার্স করুন সেটি অর্ডারে আনার জন্য।
- তারপর বাকি এলিমেন্টের রেঞ্জ রিভার্স করুন, অর্থাৎ k থেকে N-1 পর্যন্ত।
উদাহরণ প্রোগ্রাম
using namespace std;
#include <bits/stdc++.h>
void reverse(int nums[], int start, int end) {
int temp = 0;
// স্ট্রাট এলিমেন্টকে এন্ড এলিমেন্ট দিয়ে সোয়্যাপ করে অ্যারে রিভার্স করা।
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;
// পুরো অ্যারে রিভার্স করা
reverse(arr, 0, N - 1);
k = k % N;
// 0 থেকে k-1 পর্যন্ত এলিমেন্ট রেঞ্জ রিভার্স করা।
reverse(arr, 0, k - 1);
// k থেকে শেষ এলিমেন্ট পর্যন্ত এলিমেন্ট রেঞ্জ রিভার্স করা।
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, ইত্যাদি। আশা করি আপনি এই আর্টিকেলটিকে সহায়ক খুঁজে পাবেন।
