C++で配列内の他の要素で割り切れる要素を出力する方法

問題の概要

この記事では、整数の配列が与えられたときに、配列内の他の少なくとも1つの要素で割り切れる数だけを出力する方法を解説します。

まず、具体的な例で問題を確認しましょう。

入力 : 3 12 16 21
出力 : 12 21

解説: 3は配列内で最小の要素のため、他の要素で割り切れる可能性がありません。12は3で割り切れ、16は3で割り切れませんが、21は3で割り切れます。したがって、3と16を除外し、12と21のみを出力します。

単純なアプローチとその課題

最も直感的な方法は、各要素について配列内の他のすべての要素で割り切れるかどうかを順番に確認することです。しかし、この総当たり方式はO(N²)の時間計算量を必要とするため、要素数が多い場合には非効率になります。

ハッシュを使った効率的な解法

より効率的なのが、ハッシュセット(unordered_set)を活用する方法です。基本的な流れは以下の通りです。

1. 配列の全要素をハッシュセットに格納し、同時に配列内の最大値を求めます。
2. 各要素について、その2倍から最大値までの倍数を順に調べ、倍数がハッシュセット内に存在すれば、その倍数は「少なくとも1つの要素で割り切れる」ことになります。
3. 同じ値が複数回出現する場合は、互いに割り切れるため出力対象に含めます。

サンプルコード

この考え方に基づいて、C++でプログラムを作成すると以下のようになります。

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

// 他の要素で割り切れる要素を出力する関数
void printDivisibleNumber(int arr[], int n){
    unordered_set<int> s;      // 配列の全要素を格納するハッシュセット
    int maxElement = INT_MIN;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
        maxElement = max(maxElement, arr[i]);
    }
    unordered_set<int> res;    // 割り切れることが確定した要素を記録
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {
            // arr[i] の倍数を最大値まで順に調べる
            for (int j = arr[i] * 2; j <= maxElement; j += arr[i]) {
                if (s.find(j) != s.end())
                    res.insert(j);
            }
        }
    }
    // 各値の出現回数をカウント(重複要素への対応)
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        mp[arr[i]]++;
    unordered_map<int, int>::iterator it;
    vector<int> ans;
    for (it = mp.begin(); it != mp.end(); it++) {
        // 同じ値が2回以上出現する場合は互いに割り切れるので出力対象
        if (it->second >= 2) {
            if (res.find(it->first) == res.end()) {
                int val = it->second;
                while (val--)
                    ans.push_back(it->first);
            }
        }
        if (res.find(it->first) != res.end()) {
            int val = it->second;
            while (val--)
                ans.push_back(it->first);
        }
    }
    for (auto x : ans)
        cout << x << "\t";
}

int main(){
    int arr[] = {2, 4, 7, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    printDivisibleNumber(arr, n);
    return 0;
}

出力結果

12 14 4

この例では、4は2で、12は2と4で、14は2と7でそれぞれ割り切れるため出力されます。一方、2は他のどの要素でも割り切れないため除外されます。

計算量について

このアルゴリズムは、各要素の倍数を最大値まで走査します。計算量は要素の値の分布に依存しますが、総当たり方式のO(N²)と比較して、特に大きな値を含む配列では大幅な高速化が期待できます。必要な追加メモリはハッシュセットとマップの分だけで、空間計算量はO(N)です。