配列の全要素から作れる数が3で割り切れるかどうかを判定するC/C++プログラム

ある数が3で割り切れるかどうかを調べるには、その数を構成する各桁の数字をすべて足し合わせ、その合計が3で割り切れるかを確認します。これが有名な「3の倍数判定法」です。

本記事では、整数型の配列 arr[] が与えられたとき、これらの要素を組み合わせて作られる数が3で割り切れるかどうかを判定する方法を解説します。割り切れる数を作れる場合は「Yes」を、作れない場合は「No」を出力します。

入力：arr[] = {45, 51, 90}
出力：Yes

考え方

この問題では、配列内の数字を並び替え・組み合わせることで、3で割り切れる数を作れるかを判定します。上記の入力例であれば、たとえば 945510 という3の倍数を構成できます。したがって、答えは「Yes」となります。

判定のポイントは、実際に数を作って割り算を行う必要がないところです。ある数の各桁の合計を3で割った余りが0であれば、その数自体も必ず3で割り切れます。さらに、数そのものを3で割った余りは、その各桁の合計を3で割った余りと等しいという剰余の性質があるため、配列の各要素を順番に加算しながら3の剰余を取っていくだけで効率よく判定できます。

アルゴリズムの手順

1. 変数 rem を 0 で初期化します。
2. 配列の各要素について、rem に要素を加えた値の3での余りを rem に代入していきます。
3. ループ終了後、rem が 0 であれば「Yes」を、そうでなければ「No」を出力します。

C言語での実装例

#include <stdio.h>

int main() {
    int arr[] = { 45, 51, 90 };
    int n = 3;
    int rem = 0;

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

    if (rem == 0)
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

出力結果

Yes

計算量

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。大きな数を実際に構築して割り算を行う必要がないため、オーバーフローの心配もありません。