समस्या विवरण
धनात्मक पूर्णांकों की एक सरणी nums दी गई है। हमें सरणी का कोई सबसेट चुनना है, प्रत्येक तत्व को एक पूर्णांक से गुणा करना है, और उन्हें जोड़ना है। यदि हम किसी सबसेट और गुणकों का उपयोग करके योग 1 प्राप्त कर सकते हैं, तो सरणी "गुड" (good) है।
उदाहरण
इनपुट
[12, 23, 7, 5]
आउटपुट
True (1)
व्याख्या: 5×3 + 7×(-2) = 15 - 14 = 1
समाधान दृष्टिकोण (बेजू की पहचान - Bézout's Identity)
संख्याओं के समुच्चय का महत्तम समापवर्तक (GCD) यदि 1 है, तो उनके पूर्णांक रैखिक संयोजन से 1 प्राप्त किया जा सकता है।
एल्गोरिदम: सरणी के सभी तत्वों का GCD निकालें। यदि GCD = 1, तो गुड ऐरे है।
कार्यकारी प्रोग्राम
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int gcd(int a, int b) {
return b == 0 ? 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) ? "True" : "False");
return 0;
}
आउटपुट
True
