在 C++ 中检查它是否为一个好的数组

假设我们有一个名为 nums 的正整数数组。我们必须选择 nums 的某个子集，然后将每个元素乘以一个整数并添加所有这些数字。如果通过任何可能的子集和乘数我们可以从数组中得到 1 的和，那么该数组将是一个好数组。

我们必须检查该数组是否好。

因此，如果输入类似于 [12,23,7,5]，则输出将为 True，这是因为如果我们取数字 5 和 7，则 5*3 + 7*(-2) = 1

为了解决这个问题，我们将遵循以下步骤 −

• g := nums[0]

• 对于初始化 i := 1，当 i < nums 的大小，更新（将 i 增加 1），则 −

  • g := g 和 nums[i] 的的最大公约数

• 当 g 为 1 时，返回 true

让我们看看以下实现来更好地理解 −

示例

 现场演示

#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

Arnab Chakraborty

更新于： 04-Jun-2020

2K+ 浏览量

开启你的 职业 生涯

完成课程以获得认证

开始