C++에서 좋은 배열인지 확인

<시간/>

양의 정수의 숫자라는 배열이 있다고 가정합니다. 숫자의 일부 하위 집합을 선택한 다음 각 요소에 정수를 곱하고 이 숫자를 모두 더해야 합니다. 가능한 부분집합과 피승수로 배열에서 합 1을 얻을 수 있다면 배열은 좋은 배열이 될 것입니다.

배열이 좋은지 아닌지 확인해야 합니다.

따라서 입력이 [12,23,7,5]와 같으면 출력은 True가 됩니다. 이는 숫자 5, 7을 취하면 5*3 + 7*(-2) =1이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

g :=숫자[0]
for initialize i :=1, i
- 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}