সমস্যা বিবরণ
লিডিং জিরো ছাড়া একটি সংখ্যা N দেওয়া আছে। N কে ২৫ দিয়ে বিভাজ্য করার ন্যূনতম কতগুলো মুভ দরকার তা বের করতে হবে। প্রতিটি মুভে যেকোনো دوটি সন্নিহিত অঙ্ক 스왪 (swap) করা যাবে এবং যেকোনো সময় সংখ্যাতে লিডিং জিরো থাকবে না। যদি সম্ভব না হয় তবে -১ প্রিন্ট করুন।
যদি N = 5071 হয়, তবে ৪টি মুভ দরকার:
5071 → 5701 → 7501 → 7510 → 7150
এলগরিদম
1. সংখ্যাটির সব অঙ্কের জোড়া ওপর ইটারেট করুন। প্রথম অঙ্কটি পজিশন 'i'-তে এবং দ্বিতীয়টি 'j'-তে। 2. এই দুটি অঙ্ককে সংখ্যাটির শেষ দুটি পজিশনে নিয়ে আসুন। 3. যদি সংখ্যাটিতে লিডিং জিরো থাকে, তবে বামপাশের প্রথম নন-জিরো অঙ্ক খুঁজে প্রথম পজিশনে নিয়ে আসুন। 4. যদি বর্তমান সংখ্যা ২৫ দিয়ে বিভাজ্য হয়, তবে সোয়াপের সংখ্যা দিয়ে আন্সার আপডেট করুন।
উদাহরণ কোড
#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;
int requiredMoves(long long n) {
string str = to_string(n);
int ans = INT_MAX;
int len = str.size();
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
if (i == j)
continue;
string temp = str;
int cnt = 0;
for (int k = i; k < len - 1; ++k) {
swap(temp[k], temp[k + 1]);
++cnt;
}
for (int k = j - (j > i); k < len - 2; ++k) {
swap(temp[k], temp[k + 1]);
++cnt;
}
int pos = -1;
for (int k = 0; k < len; ++k) {
if (temp[k] != '0') {
pos = k;
break;
}
}
for (int k = pos; k > 0; --k) {
swap(temp[k], temp[k - 1]);
++cnt;
}
long long num = atoll(temp.c_str());
if (num % 25 == 0)
ans = min(ans, cnt);
}
}
if (ans == INT_MAX)
return -1;
return ans;
}
int main() {
int n = 5071;
cout << "Minimum required moves: " << requiredMoves(n) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum required moves: 4
