【C++】配列の全要素の数字を使って3で割り切れる数を作成できるか判定する方法

問題概要

この問題では、整数型の配列が与えられます。配列の各要素を構成するすべての数字を組み合わせて1つの数を作り、その数が3で割り切れるかどうかを判定します。割り切れる場合は “Yes” を、そうでない場合は “No” を出力してください。

入出力例

具体例を見ながら問題を理解しましょう。

入力 − arr = {3, 5, 91}

出力 − YES

説明 − 配列の数字を組み合わせると、たとえば 5193 という数が作れます。5193 は 3 で割り切れるため、答えは YES となります。

解法のポイント：3の倍数の判定規則

この問題を効率よく解くカギとなるのが、次の3の倍数の判定規則です。

ある数の各桁の数字の合計が3で割り切れるならば、その数は必ず3で割り切れる。

つまり、実際に大きな数を組み立てる必要はありません。配列の全要素の合計値を求め、それが3で割り切れるかどうかを確認するだけで判定できます。これは、各要素の「桁の合計」を3で割った余りは、その要素自身を3で割った余りと等しくなるためです。

アルゴリズムの手順

1. 変数 rem を0で初期化し、配列の各要素について「(rem + 要素) % 3」を繰り返し計算して余りを更新していきます。
2. 最終的に rem が 0 であれば、作成可能な数は3で割り切れるので YES を返します。
3. rem が 0 以外の場合は NO を返します。

実装例

以下は、上記の解法を実装したC++プログラムです。

#include <iostream>
using namespace std;

bool is3DivisibleArray(int arr[], int n) {
    int rem = 0;
    for (int i = 0; i < n; i++)
        rem = (rem + arr[i]) % 3;
    return (rem == 0);
}

int main(){
    int arr[] = { 23, 64, 87, 12, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "配列の数字から作成できる数は";
    is3DivisibleArray(arr, n) ? cout << "3で割り切れます"
                              : cout << "3で割り切れません";
    return 0;
}

実行結果

配列の数字から作成できる数は3で割り切れます

計算量

• 時間計算量： O(n) — 配列の要素を一度だけ走査します。
• 空間計算量： O(1) — 余りを保持する変数1つだけで済みます。

まとめ

この問題は、「ある数が3で割り切れる ⇔ 各桁の合計が3で割り切れる」という性質を利用することで、数を実際に構築せずに配列の合計の余りを計算するだけで解けます。非常にシンプルで高速な線形時間アルゴリズムとして実装できるのがポイントです。