ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যার সংখ্যা নামে একটি অ্যারে আছে। আমাদের কিছু সংখ্যার উপসেট নির্বাচন করতে হবে, তারপর প্রতিটি উপাদানকে একটি পূর্ণসংখ্যা দ্বারা গুণ করতে হবে এবং এই সমস্ত সংখ্যা যোগ করতে হবে। অ্যারেটি একটি ভাল অ্যারে হবে যদি আমরা যেকোনো সম্ভাব্য উপসেট এবং গুণিতক দ্বারা অ্যারে থেকে 1 এর যোগফল পেতে পারি।
আমাদের পরীক্ষা করতে হবে অ্যারেটি ভালো কি না।
সুতরাং, যদি ইনপুটটি [12,23,7,5] এর মত হয়, তাহলে আউটপুটটি True হবে, কারণ আমরা যদি 5, 7 সংখ্যা নিই, তাহলে 5*3 + 7*(-2) =1 পি>
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
g :=সংখ্যা[0]
-
আরম্ভ করার জন্য i :=1, যখন i <সংখ্যার আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −
-
g :=g এবং সংখ্যার gcd[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} আউটপুট
1
