C++で3で割り切れるが6で割り切れない数nの順列を求める方法

問題の概要

ある数nが与えられたとき、その桁を並べ替えた順列の中から「3で割り切れるが、6では割り切れない」数を見つけることを考えます。そのような値を作ることができない場合は、-1を返します。例えば、nが336の場合、答えの候補として363が出力されます。

解法の考え方

ご存知の通り、6で割り切れる数とは、3と2の両方で割り切れる数のことです。つまり、3で割り切れる偶数は必ず6でも割り切れます。そこで、3で割り切れかつ偶数である数の桁を入れ替えて奇数にすることができれば、その数が求める答えとなります。

ここで重要なポイントとして、桁を並べ替えても各位の数字の合計は変わらないため、元の数が3で割り切れれば、そのすべての順列も必ず3で割り切れます。したがって、判定が必要なのは「奇数になる並べ替えが存在するかどうか」だけです。少なくとも1つの桁に奇数が含まれていれば答えが存在し、すべての桁が偶数であれば-1を返すことになります。

具体的な手順は以下の通りです。

1. 数がすでに奇数であれば、そのまま答えとして返します。
2. 偶数であれば、最下位の桁を最上位へ移動させる（桁を回転させる）操作を繰り返し、その都度奇数かどうかを判定します。
3. 桁数と同じ回数だけ回転を試しても奇数にならなければ、-1を返します。

実装例（C++）

#include <iostream>
#include <cmath>
using namespace std;

// 3で割り切れるが6で割り切れない順列を探す関数
int findNumber(int n) {
    int digit_count = ceil(log10(n)); // 桁数を求める
    for (int i = 0; i < digit_count; i++) {
        if (n % 2 != 0) {
            return n; // 奇数ならそのまま答え
        } else {
            // 最下位の桁を最上位へ移動（右回転）
            n = (n / 10) + (n % 10) * pow(10, digit_count - i - 1);
            continue;
        }
    }
    return -1; // 見つからなければ-1を返す
}

int main() {
    int n = 132;
    cout << "3で割り切れるが6で割り切れない" << n << "の順列は:" << findNumber(n);
}

出力結果

3で割り切れるが6で割り切れない132の順列は:213

動作の解説

入力が132の場合、最初は偶数なので、最下位の桁「2」を最上位へ移動すると213になります。213は奇数であり、各桁の和が2+1+3=6で3の倍数であるため、3で割り切れますが、奇数なので6では割り切れません。したがって、213が正解として返されます。

このアルゴリズムの計算量は、桁の回転を最大で桁数回行うだけなので、桁数をdとするとO(d)となり、非常に効率的です。