在 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

更新於： 04-Jun-2020

2K+ 瀏覽量

開啟你的 職業 生涯

完成課程以獲得認證

開始
廣告