C++ का उपयोग करके N को 25 से विभाज्य बनाने के लिए आवश्यक दी गई चालों की न्यूनतम संख्या।

समस्या कथन

बिना अग्रणी शून्य के एक संख्या N दी गई है। कार्य N को 25 से विभाज्य बनाने के लिए आवश्यक न्यूनतम चालों को खोजना है। प्रत्येक चाल पर, कोई भी दो आसन्न अंकों को स्वैप कर सकता है और यह सुनिश्चित कर सकता है कि किसी भी समय संख्या में कोई अग्रणी शून्य नहीं होना चाहिए। यदि N को 25 से विभाज्य बनाना संभव नहीं है तो प्रिंट करें -1

यदि N =5071 तो इसे 25 से विभाज्य बनाने के लिए 4 चालों की आवश्यकता है

5071 → 5701 → 7501 → 7510 → 7150

एल्गोरिदम

1. Iterate over all pairs of digits in the number. Let the first digit in the pair is at position ‘i’ and the second is at position ‘j’.
2. Place these digits to the last two positions in the number
3. If the number has a leading zero. Find the leftmost nonzero digit and move it to the first position.
4. If the current number is divisible by 25 then update the answer with the number of swaps

उदाहरण

#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