C++で適切な配列かどうかを確認します

正の整数のnumsという配列があるとします。 numのサブセットを選択してから、各要素に整数を掛けて、これらすべての数値を加算する必要があります。可能なサブセットと被乗数によって配列から合計1を取得できれば、配列は適切な配列になります。

アレイが良好かどうかを確認する必要があります。

したがって、入力が[12,23,7,5]の場合、出力はTrueになります。これは、5、7、5 * 3 + 7 *（-2）=1

これを解決するには、次の手順に従います-

• g：=nums [0]

• 初期化i：=1の場合、i

  • g：=gとnumsのgcd[i]

• 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