ตรวจสอบว่าเป็นอาร์เรย์ที่ดีหรือไม่ใน C++

สมมติว่ามีอาร์เรย์ nums ของจำนวนเต็มบวก เราเลือก subset ของ nums คูณแต่ละตัวด้วยจำนวนเต็มแล้วบวกกัน อาร์เรย์จะเป็น "ดี" ถ้าเราสามารถได้ผลรวม 1 จาก subset และตัวคูณใดๆ

เช่น [12,23,7,5] เป็นอาร์เรย์ที่ดี เพราะ 5*3 + 7*(-2) = 1

วิธีแก้ − คำนวณ GCD ของทุกตัวเลขในอาร์เรย์ ถ้า GCD = 1 คืออาร์เรย์ดี (ทฤษฎีจำนวนเบ祖)

ตัวอย่าง

#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