Giả sử chúng ta có một mảng gọi là nums chứa các số nguyên dương. Chúng ta phải chọn một tập con của nums, sau đó nhân mỗi phần tử với một số nguyên và cộng tất cả các số này. Mảng sẽ là mảng tốt nếu chúng ta có thể được tổng bằng 1 từ mảng bằng bất kỳ tập con và hệ số nhân nào.
Chúng ta phải kiểm tra xem mảng có tốt hay không.
Vì vậy, nếu đầu vào giống như [12,23,7,5], thì đầu ra sẽ là True, vì nếu chúng ta lấy số 5, 7, thì 5*3 + 7*(-2) = 1
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
g := nums[0]
for khởi tạo i := 1, khi i < kích thước của nums, cập nhật (tăng i lên 1), thực hiện −
g := gcd của g và nums[i]
trả về true khi g bằng 1
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#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)); } Đầu vào
{12,23,7,5} Đầu ra
1