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

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

เราต้องเช็คก่อนว่าอาร์เรย์ดีหรือไม่

ดังนั้นหากอินพุตเป็น [12,23,7,5] ผลลัพธ์จะเป็น True นั่นก็เพราะ หากเราเอาตัวเลข 5, 7 แล้ว 5*3 + 7*(-2) =1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

g :=nums[0]
สำหรับการเริ่มต้น i :=1 เมื่อฉัน <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -
- g :=gcd ของ g และ nums[i]
คืนค่า จริง เมื่อ g เป็น 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}