Kiểm tra xem nó có phải là một mảng tốt trong C ++ hay không

Giả sử chúng ta có một mảng được gọi là nums các số nguyên dương. Chúng ta phải chọn một số tập hợp con của các số, sau đó nhân từng phần tử với một số nguyên và cộng tất cả các số này. Mảng sẽ là một mảng tốt nếu chúng ta có thể lấy tổng là 1 từ mảng bằng bất kỳ tập con và phép nhân nào có thể có.

Chúng ta phải kiểm tra xem mảng có tốt hay không.

Vì vậy, nếu đầu vào là [12,23,7,5], thì đầu ra sẽ là Đúng, điều này là do Nếu chúng ta lấy các số 5, 7 thì 5 * 3 + 7 * (- 2) =1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• g:=nums [0]

• để khởi tạo i:=1, khi tôi

  • g:=gcd của g và nums [i]

• trả về true khi g là 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{12,23,7,5}

Đầu ra

1