【C++】3で割り切れる数にするために削除が必要な最小の桁数を求める方法

文字列として与えられた数値から、いくつかの桁を取り除くことで3の倍数(3で割り切れる数)にすることを考えます。この記事では、3で割り切れる数にするために削除が必要な最小の桁数を求めるアルゴリズムと、C++での実装方法をわかりやすく解説します。

問題のポイント

この問題には重要な性質があります。それは、どんな数でも最大2桁の削除で3の倍数にできるという点です。

理由は次のとおりです。数を3で割った余りは、各桁の数字の合計を3で割った余りと等しくなります。各桁の数字の3で割った余りは「0」「1」「2」のいずれかなので、合計の余りが1なら「余り1」の桁を1つ、余りが2なら「余り2」の桁を1つ削除すればよいことになります。該当する桁が存在しない場合でも、「余り2」の桁を2つ削除すれば合計の余りを調整できます。したがって、答えは必ず0〜2の範囲に収まり、どうしても作れない場合のみ-1を返します。

入出力例

例1

入力

92

出力

1

「2」を削除すると「9」となり、9は3で割り切れます。削除する桁数は1で済みます。

例2

入力

999

出力

0

与えられた数自体がすでに3の倍数なので、削除は不要です。

アルゴリズム

• 数値を文字列として初期化します。

• 各桁の数字の合計を求めます。

• 合計が3で割り切れる場合は、0 を返します。

• 合計が3で割り切れず、桁数が1の場合は、これ以上削除できないため -1 を返します。

• 各桁を順に走査します。

  • その桁を1つ削除したときに3で割り切れるか(合計の余りとその桁の余りが一致するか)を確認します。

  • 条件を満たせば、1 を返します。

• 再度桁数を確認し、桁数が 2 の場合は、2桁すべて削除すると数が成立しないため -1 を返します。

• それ以外の場合は 2 を返します。

C++での実装

以下は、上記アルゴリズムをC++で実装したコードです。

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

// 各桁の数字の合計を求める
int getNumSum(string n) {
    int len = n.length(), sum = 0;
    for (int i = 0; i < len; i++) {
        sum += n[i] - '0';
    }
    return sum;
}

// 削除が必要な最小の桁数を求める
int getDigitsCount(string num) {
    int n = num.length();
    int sum = getNumSum(num);

    // すでに3の倍数の場合
    if (sum % 3 == 0) {
        return 0;
    }

    // 1桁しかない場合は削除できない
    if (n == 1) {
        return -1;
    }

    // 1桁削除で3の倍数にできるか確認
    for (int i = 0; i < n; i++) {
        int currentDigit = num[i] - '0';
        if (sum % 3 == currentDigit % 3) {
            return 1;
        }
    }

    // 2桁の場合は2桁削除できない
    if (n == 2) {
        return -1;
    }

    // 2桁削除すれば必ず3の倍数にできる
    return 2;
}

int main() {
    string num = "7536836";
    cout << getDigitsCount(num) << endl;
    return 0;
}

コードの解説

getNumSum 関数では、文字の各桁を数値として扱うために n[i] - '0' で文字コードから実際の数字へ変換しています。getDigitsCount 関数が本体で、まず合計が3の倍数かどうかを判定し、次に「1桁だけ削除すればよいか」を各桁の余りと比較することで効率よく求めています。最後まで条件を満たす桁が見つからなければ、残る選択肢は2桁の削除のみです。

出力

上記のコードを実行すると、次の結果が得られます。

1

入力「7536836」の場合、各桁の合計は38となり、3で割ると余り2です。「5」や「8」のように3で割った余りが2になる桁を1つ削除すれば3の倍数になるため、答えは1となります。

計算量

• 時間計算量: O(n)(nは桁数。文字列を数回走査するだけです)

• 空間計算量: O(1)(追加のメモリは定数個の変数のみ)