C++-এ ভালো অ্যারে (Good Array) চেক করা

একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে nums দেওয়া আছে। আমরা এর একটি সাবসেট বেছে নিতে পারি, প্রতিটি এলিমেন্টকে একটি পূর্ণসংখ্যা দিয়ে গুণ করতে পারি, এবং তারপর সেগুলো যোগ করতে পারি। অ্যারেটি "ভালো অ্যারে" (good array) হবে যদি আমরা যেকোনো সাবসেট এবং গুণক ব্যবহার করে যোগফল ১ পেতে পারি।

উদাহরণ

ইনপুট: [12, 23, 7, 5] → আউটপুট: true

ব্যাখ্যা: ৫ এবং ৭ বেছে নিয়ে 5*3 + 7*(-2) = 15 - 14 = 1 পাওয়া যায়।

সমাধানের পদ্ধতি

এটি একটি ক্লাসিক সংখ্যা তত্ত্ব সমস্যা। বেজূ identidad (Bezout's identity) অনুযায়ী, কিছু পূর্ণসংখ্যার লিনিয়ার কম্বিনেশন দিয়ে ১ পাওয়া যায় যদি এবং কেবল যদি তাদের GCD (সর্বোচ্চ সাধারণ ভাজক) ১ হয়।

সুতরাং, পুরো অ্যারের GCD বের করুন। যদি GCD = ১ হয়, তবে এটি ভালো অ্যারে।

প্রোগ্রাম উদাহরণ

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

int main() {
    Solution ob;
    vector<int> v = {12, 23, 7, 5};
    cout << (ob.isGoodArray(v));
}

ইনপুট

{12, 23, 7, 5}