C++で数値Nを25で割り切れるようにするための最小移動回数を求める方法

問題の概要

先頭にゼロが付かない数値 N が与えられます。この問題の目的は、N を 25 で割り切れるようにするために必要な移動（隣り合う 2 桁の入れ替え）の最小回数を求めることです。ただし、どの時点においても数値の先頭がゼロになってはいけません。どのように操作しても N を 25 の倍数にできない場合は、-1 を出力します。

例えば、N = 5071 の場合、25 で割り切れる状態にするには 4 回の移動が必要です。

5071 → 5701 → 7501 → 7510 → 7150

ポイント：25 の倍数の性質

ある整数が 25 で割り切れるのは、その末尾 2 桁が「00」「25」「50」「75」のいずれかになっている場合です。つまり、この問題は「元の数字列から適切な 2 桁を選び、それらを末尾 2 桁の位置へ移動させるのに必要な隣接スワップの最小回数を求める」問題として捉えることができます。

アルゴリズム

1. 数値内のすべての桁のペアを走査します。ペアの 1 つ目の桁の位置を i、2 つ目の桁の位置を j とします。
2. 選んだ 2 つの桁を、それぞれ数値の最後から 2 番目と最後の位置へ移動させます。
3. 先頭にゼロが現れた場合は、左端にある非ゼロの桁を探し、それを先頭の位置まで移動させます。
4. その結果得られた数値が 25 で割り切れる場合、必要だったスワップ回数で答えを更新します。

すべてのペアに対して上記の手順を試し、最終的に残った最小値が答えとなります。一度も 25 の倍数を作れなかった場合は -1 を返します。

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

計算量について

桁数を n とすると、調べるべき桁のペアは最大 O(n²) 通り存在します。さらに各ペアごとに O(n) 回程度のスワップと先頭ゼロの解消処理が必要となるため、全体の計算量は O(n³) となります。桁数がそれほど多くない入力に対しては十分実用的なアプローチです。