C++で配列が「良い配列（Good Array）」かどうかを判定する方法

問題の概要

正の整数からなる配列 nums が与えられたとします。この中から任意の部分集合を選び、各要素に整数（負の値も可）を掛け合わせたうえで、それらをすべて足し合わせます。どのような部分集合や係数の組み合わせを選んでも合計を 1 にできるとき、その配列は「良い配列（good array）」であると定義されます。

つまり、この記事の課題は、与えられた配列が良い配列かどうかを判定することです。

例として、入力が [12, 23, 7, 5] の場合を考えてみましょう。このとき出力は True になります。なぜなら、5 と 7 を選べば 5×3 + 7×(−2) = 1 という計算が成立するからです。

解決のアプローチ

この問題は、数論の基本的な定理である「ベズーの等式（Bézout's identity）」を利用すると効率よく解けます。ベズーの等式によれば、2つの整数 a と b の最大公約数（GCD）を g とすると、ax + by = g を満たす整数 x, y が必ず存在します。これを配列全体に拡張すると、配列全体の GCD が 1 であれば、適切な係数を選ぶことで合計 1 を必ず作れることが分かります。逆に GCD が 1 より大きければ、どんな組み合わせでも合計は g の倍数になり、1 にはなりません。

具体的な手順は次の通りです。

• 変数 g を nums[0] で初期化します。

• i := 1 から配列の末尾までループし、各要素に対して次を実行します。

  • g := g と nums[i] の最大公約数（GCD）

• 最終的に g が 1 であれば true を返します。

それでは、以下の実装例を見て理解を深めましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int gcd(int a, int b){
        return !b ? a : gcd(b, a % b);
    }
    bool isGoodArray(vector<int>& nums){
        int g = nums[0];
        for (int i = 1; i < nums.size(); i++)
        g = gcd(g, nums[i]);
        return g == 1;
    }
};
main(){
    Solution ob;
    vector<int> v = {12,23,7,5};
    cout << (ob.isGoodArray(v));
}

入力

{12,23,7,5}

出力

1

出力の 1 は true を意味します。つまり {12, 23, 7, 5} は良い配列であると判定されました。

まとめ

このアルゴリズムの計算量は O(n log(max(nums))) であり、配列の長さに比例して処理できます。全要素の GCD を一度求めるだけで判定できるため、シンプルかつ高速な解法といえます。