【C++】他のすべての要素の合計を割り切る配列要素の個数を数える方法

本記事では、整数値からなる配列 arr[] が与えられたとき、「その要素自身を除いた残りの要素の合計を割り切れる要素」が配列の中にいくつあるかを求める方法を解説します。

配列とは、同じ型の要素を固定長で連続的に格納できるデータ構造です。複数のデータをまとめて扱うことができ、同じ型の変数の集合として考えると理解しやすくなります。

具体例

入力: int arr_1[] = {9, 6, 3}
出力: count is 3

説明: 要素 9 に対しては残りの合計 6+3 = 9 が 9 で割り切れ、要素 6 に対しては 9+3 = 12 が 6 で割り切れ、要素 3 に対しては 9+6 = 15 が 3 で割り切れます。したがって、条件を満たす要素は 3 個となります。

入力: arr[] = {3, 10, 4, 6, 7}
出力: count is 3

説明: 要素 3 に対しては 10+4+6+7 = 27 が 3 で割り切れ、要素 10 に対しては 3+4+6+7 = 20 は 10 で割り切れないためカウントされません。要素 4 に対しては 3+10+6+7 = 26 は 4 で割り切れませんが、要素 6 に対しては 3+10+4+7 = 24 が 6 で割り切れ、要素 7 に対しては 3+10+4+6 = 23 は 7 で割り切れません。条件を満たすのは 3・10・6 の 3 個となります。

アルゴリズムの考え方

• 配列 arr[] を用意します。
• length() 関数（または sizeof 演算子）を使って配列のサイズを取得します。戻り値は配列内の要素数に対応する整数値です。
• 条件を満たす要素の個数を格納する一時変数（カウンタ）を用意します。
• i を 0 から配列サイズ未満まで動かすループを開始します。
• ループ内で、注目している要素以外の合計を格納する変数 temp を 0 で初期化します。
• さらに内側のループとして、j を 0 から配列サイズ未満まで動かします。
• i == j の場合（自分自身を指している場合）はスキップします。
• それ以外の場合は、temp に arr[j] を加算していきます。
• 内側のループ終了後、temp % arr[i] == 0 であれば、カウンタの値を 1 増やします。
• すべてのループが終わったらカウンタを返します。
• main 関数側で結果を出力します。

実装例

#include <iostream>
using namespace std;

int countelements(int arr_1[], int size){
    // 条件を満たす要素の個数を格納する変数
    int result = 0;
    for (int i = 0; i < size; i++){
        // 合計を 0 で初期化
        int sum = 0;
        for (int j = 0; j < size; j++){
            if (i == j){
                continue; // 自分自身は除外
            }
            else{
                sum += arr_1[j];
            }
        }
        // 残りの合計が選んだ要素で割り切れる場合
        if (sum % arr_1[i] == 0){
            result++;
        }
    }
    // 個数を返す
    return result;
}

// main 関数
int main(){
    int arr_1[] = { 1, 2, 3, 4, 5, 6 };
    int size = sizeof(arr_1) / sizeof(arr_1[0]);
    cout << "count is " << countelements(arr_1, size);
    return 0;
}

出力結果

上記のコードを実行すると、次のような出力が得られます。

count is 2

この例では、配列 {1, 2, 3, 4, 5, 6} の中で「自分以外の合計を割り切れる」要素は 2 個（例：要素 1 と要素 5）であることを示しています。

このアルゴリズムの計算量は O(N²) です。各要素について残りの要素の合計を毎回計算し直すため、配列のサイズが大きくなると処理時間が増加します。あらかじ配列全体の総和を求めておき、各要素ごとに「総和 − 自身の値」を計算すれば、O(N) まで効率化できる点も覚えておくと便利です。