समस्या कथन
अग्रणी शून्य के बिना एक संख्या N दी गई है। N को 25 से विभाज्य बनाने के लिए आवश्यक न्यूनतम मूव्स की संख्या ढूंढें। प्रत्येक मूव में, कोई भी दो आसन्न अंकों को स्वैप कर सकता है और यह सुनिश्चित करना होगा कि किसी भी समय संख्या में कोई अग्रणी शून्य न हो। यदि N को 25 से विभाज्य बनाना संभव नहीं है तो -1 प्रिंट करें।
यदि N=5071, तो 25 से विभाज्य बनाने के लिए 4 मूव्स आवश्यक हैं:
5071 → 5701 → 7501 → 7510 → 7150
एल्गोरिदम
1. संख्या में अंकों के सभी जोड़ों पर पुनरावृति करें। मान लें जोड़ी में पहला अंक स्थिति 'i' पर है और दूसरा स्थिति 'j' पर। 2. इन अंकों को संख्या में अंतिम दो स्थितियों पर रखें 3. यदि संख्या में अग्रणी शून्य है। बाएं सबसे दूर के गैर-शून्य अंक को ढूंढें और इसे पहली स्थिति पर ले जाएं। 4. यदि वर्तमान संख्या 25 से विभाज्य है तो स्वैप की संख्या के साथ उत्तर अपडेट करें
C++ उदाहरण
#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