আমাদের ১ থেকে n পর্যন্ত সংখ্যা যাতে একটি অ্যারে দেওয়া আছে (রিপিট নেই)। 'move-to-front' অপারেশন হলো একটি এলিমেন্ট নিয়ে সেটি প্রথমে (ইন্ডেক্স ০) রাখা। লক্ষ্য অ্যারে সর্টেড করার জন্য ন্যূনতম ऐसी অপারেশন বের করা।
অ্যারেটি শেষ থেকে ট্র্যাভার্স: যদি এলিমেন্ট সঠিক পজিশনে থাকে (arr[i] == i+1) তবে মুভ লাগে না। অন্যথায় মুভ লাগে।
ইনপুট
Arr[]= { 4,3,2,1 }
আউটপুট
Minimum move-to-front operations: 3
ব্যাখ্যা: ৩ মুভ -> 3,4,2,1 -> 2,3,4,1 -> 1,2,3,4।
ইনপুট
Arr[]= { 6,1,2,5,4,3 }
আউটপুট
Minimum move-to-front operations: 5
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- movetoFront(int arr[], int n) ফাংশন।
- count = n (সর্বোচ্চ সবাই মুভ হতে পারে)।
- i=n-1 থেকে ০ পর্যন্ত: যদি arr[i] == count হয় তবে count-- (সঠিক পজিশনে আছে)।
- শেষে count রিটার্ন (ন্যূনতম মুভ)।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int movetoFront(int arr[], int n){
int count = n;
for (int i = n-1; i >= 0; i--){
if (arr[i] == count)
count--;
}
return count;
}
int main(){
int Arr[] = {5, 3, 4, 7, 2, 6, 1};
int size = 7;
cout << "Minimum 'move-to-front' to sort array:" << movetoFront(Arr, size);
return 0;
}আউটপুট
Minimum 'move-to-front' to sort array:6
