C++を使用してNを25で割り切れるのに必要な所定の移動の最小数。

問題の説明

先行ゼロのない数値Nが与えられます。タスクは、Nを25で割り切れるのに必要な最小移動数を見つけることです。各移動で、隣接する2桁を入れ替えて、いつでも数値に先行ゼロが含まれていないことを確認できます。 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