সমস্যা বিবরণ
N এলিমেন্টের একটি অ্যারে এবং একটি পূর্ণসংখ্যা K দেওয়া আছে। নিচের অপারেশন যেকোনোবার করা যাবে:
- K-তম এলিমেন্টটি অ্যারের শেষে যোগ করুন এবং অ্যারের প্রথম এলিমেন্টটি ডিলিট করুন।
অ্যারের সব এলিমেন্ট সমান করতে ন্যূনতম কতগুলো মুভ দরকার তা বের করতে হবে। সম্ভব না হলে -১ প্রিন্ট করুন।
যদি arr[] = {1, 2, 3, 4, 5, 6} এবং k = 6 হয়, তবে ন্যূনতম ৫টি মুভ দরকার:
Move-1: {2, 3, 4, 5, 6, 6}
Move-2: {3, 4, 5, 6, 6, 6}
Move-3: {4, 5, 6, 6, 6, 6}
Move-4: {5, 6, 6, 6, 6, 6}
Move-5: {6, 6, 6, 6, 6, 6}
এলগরিদম
1. প্রথমে a[k]-কে শেষে কপি করুন, তারপর a[k+1] এবং এভাবে চলতে থাকুন 2. শুধু সমান এলিমেন্ট কপি হয় তা নিশ্চিত করতে, K থেকে N পর্যন্ত সব এলিমেন্ট সমান হতে হবে। ১ থেকে K এর মধ্যে a[k]-এর সাথে অসমান এলিমেন্টগুলো সরিয়ে ফেলতে হবে 3. ১ থেকে K এর রেঞ্জে ডানপাশের যে এলিমেন্ট a[k]-এর সাথে অসমান, সেটি পাওয়া পর্যন্ত অপারেশন চালিয়ে যান।
উদাহরণ কোড
#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getMinMoves(int *arr, int n, int k) {
int i;
for (i = k - 1; i < n; ++i) {
if (arr[i] != arr[k - 1]) {
return -1;
}
}
for (i = k - 1; i >= 0; --i) {
if (arr[i] != arr[k - 1]) {
return i + 1;
}
}
return 0;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6};
int k = 6;
cout << "Minimum moves required = " << getMinMoves(arr, SIZE(arr), k) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum moves required = 5
