配列のすべての要素を連結した整数が3で割り切れるかどうかを判定するC/C++プログラム

概要

本記事では、n個の数値を含む配列が与えられたとき、そのすべての要素を連結して1つの整数を作った場合に、その数が3で割り切れるかどうかを判定する方法を解説します。

例えば、配列の要素が {15, 24, 23, 13} である場合、これらを順に並べて「15242313」という整数を作ることができます。この数は3で割り切れます。

アルゴリズムのポイント

3の倍数の判定には、「ある数の各桁の数字の合計が3で割り切れるならば、その数自身も3で割り切れる」という有名な性質を利用します。

配列の要素を連結してできる数の各桁の和は、元の各数値の桁の和と一致します。また、任意の整数は「その値を3で割った余り」と「桁の和を3で割った余り」が等しいという性質を持つため、配列内の全要素の合計を3で割った余りが0になるかどうかを調べるだけで判定できます。

これにより、巨大な整数を実際に連結して生成する必要がなく、オーバーフローの心配もありません。

アルゴリズム

checkDivThree(arr)

Begin
    rem := 0
    for each element e in arr, do
        rem := (rem + e) mod 3
    done
    if rem is 0, then
        return true
    end if
    return false
End

C++での実装例

#include<iostream>
#define MAX 4
using namespace std;
bool checkDivThree(int arr[], int n){
    int rem = 0;
    for(int i = 0; i<n; i++){
        rem = (rem + arr[i]) % 3; // 各要素を加算しながら3の剰余を更新
    }
    if(rem == 0){
        return true;
    }
    return false;
}
main() {
    int arr[] = {15, 24, 23, 13};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(checkDivThree(arr, n)){
        cout << "Divisible";      // 割り切れる場合
    }else{
        cout << "Not Divisible";  // 割り切れない場合
    }
}

出力

Divisible

まとめ

このアルゴリズムは配列を一度走査するだけでよいため、時間計算量はO(n)、空間計算量はO(1)ときわめて効率的です。実際に大きな数値を生成せずに3の倍数判定が行えるため、要素数や桁数が非常に多い場合でも安全かつ高速に動作します。