C++で数nを1にするのに必要な最小操作回数を求めるプログラム

ある正の整数 n が与えられます。この n に対して、次のいずれかの操作を何度でも実行できるものとします。

• n が2で割り切れるとき、n を n/2 に置き換える

• n が3で割り切れるとき、n を 2n/3 に置き換える

• n が5で割り切れるとき、n を 4n/5 に置き換える

これらの操作を繰り返し、n を1にするまでに必要な最小の操作回数を求めてください。どうしても1にできない場合は -1 を返します。

たとえば、入力が n = 10 のとき、出力は 4 になります。具体的な手順は次のとおりです。

• n/2 の操作で 10 → 5
• 4n/5 の操作で 5 → 4
• n/2 の操作で 4 → 2
• n/2 の操作で 2 → 1

解法の考え方

この問題は貪欲法(グリーディ法)で解くことができます。n を1にするには、素因数である2・3・5をすべて取り除く必要があります。したがって、n が 2^a × 3^b × 5^c の形で表せない場合、答えは -1 になります。

また、各素因数を取り除くのに必要な操作回数は次のように考えられます。

• 2で割る場合： 操作「n → n/2」をそのまま使えるので 1回
• 3で割る場合： 「n → 2n/3」→「n/2」の2段階で n/3 に到達できるので 2回(奇数の n では 2n/3 が必ず偶数になるため有効)
• 5で割る場合： 「n → 4n/5」→「n/2」→「n/2」の3段階で n/5 に到達できるので 3回

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

m := 0
n が 1 ではない間、以下を繰り返す:
    n mod 2 が 0 の場合:
        n := n / 2
        m を 1 増やす
    そうでなく n mod 3 が 0 の場合:
        n := n / 3
        m := m + 2
    そうでなく n mod 5 が 0 の場合:
        n := n / 5
        m := m + 3
    それ以外の場合:
        m := -1
        ループを抜ける
m を返す

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    int m = 0;
    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
            m++;
        }
        else if (n % 3 == 0) {
            n = n / 3;
            m += 2;
        }
        else if (n % 5 == 0) {
            n = n / 5;
            m += 3;
        }
        else {
            m = -1;
            break;
        }
    }

    return m;
}
int main() {
    int n = 10;
    cout << solve(n) << endl;
}

入力

10

出力

4

計算量

ループの各反復で n は必ず減少していくため、時間計算量は O(log n)、空間計算量は O(1) となり、非常に効率的です。