主題

LeetCode - 1250. Check If It Is a Good Array 解題心得

Not In My Back Yard | 2022-01-16 00:00:01 | 巴幣 0 | 人氣 48

題目連結:


題目意譯:
給定一正整數陣列 nums。你的任務是選擇 nums 的一個子集合,將這些數字各自分別地乘上某個整數並加總。該陣列會被稱為「好的」如果你可以從陣列的任意可能之子集合和乘數而得到總和 1 之值。

回傳真(True)如果陣列是好的;反之則回傳假(False)。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [12,5,7,23]
輸出: true
解釋: 挑數字 5 和 7。
5 × 3 + 7 × (-2) = 1

範例 2:
輸入: nums = [29,6,10]
輸出: true
解釋: 挑數字 29 、 6 和 10。
29 × 1 + 6 × (-3) + 10 × (-1) = 1

範例 3:
輸入: nums = [3,6]
輸出: false


解題思維:
根據貝祖定理(Bézout's Lemma,更多資訊參見維基頁面):
x1 、 x2 、 …… 、xn 存在 a1 、 a2 、 …… 、an 使得
a1x1 + a2x2 + …… anxn = 1
若且唯若 x1 、 x2 、 …… 、 xn 的最大公因數為 1(即互質)。

而如果已知某一數組中所有數字的最大公因數,則再新加任意數量的正整數都只會將最大公因數變小或不變。因為本題最大公因數是 1,因此如果 nums 中存在一子集合使得最大公因數為 1,則將剩下沒挑到的數字加進來(即該子集合的補集)也只會得到最大公因數為 1。

也就是說我們可以直接求整個陣列 nums 的數字之最大公因數 C。如果 C ≠ 1 則不可能符合好陣列的定義,因此回傳假;反之則代表可能,因此回傳真。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作