1250 - true if gcd(array) is 1,  use co-primes existence for early exit
---\n\nHard to see at first, and its pure math\nA long one coming, below :)\n\n---\n\nAlgo\n\n- 1 <= nums[i] <= 10^9 So array elements are always +ve\n- For [1]
---\n\nHard to see at first, and its pure math\nA long one coming, below :)\n\n---\n\n**Algo**\n\n- `1 <= nums[i] <= 10^9` So array elements are always +ve\n- For `[1]` or `[1,2,3]` or `[1,5,10,15,20]` array is good\n  - because we have  subset as `[ 1 ]` & multiplicand as `1`, so our sum (after multiplying with each element of array with some multiplicand is `1*1`) is `1`\n- For `[5,10,15,20]`, array is not good\n  - because we dont have 1 as element\n  - so some of elements must have `-ve` numbers as `multiplicand`\n    - but even after having them, for example `5*-2 + 10*1`, it comes to `0`\n    - this is because they are all multiples of a number (`5` in this case)\n      - but we need `1`\n      - so picking multiples of number won\'t help\n      - and picking `co-primes` will help\n  - Now we know `co-primes` will help\n   - Some exampels are `[5,7]` , `[5,11]` , `[7,37]`\n     - It\'s easy to see that the gcd of 1st two is `1`, also it is also for last one\n       - But is it working really? `5*3 + 7*-2 = 1`, `5*-2 + 11*1 = 1`, `-7*21 + 4*37 = 1`, yes, it is working\n  - So, we know that if `gcd` is 1 then it is working\n- But what about `[5,10,15,20, 7]`?\n  - Here there some numbers are multiples of `5`, also `5 & 7` are `co-prime`\n    - Since we can take subset, we can take `[5,7]` and they are co-prime (`gcd = 1`), we its good\n      - How? Same as above `5*3 + 7*-2 = 1`\n      - So, effectively both `[5,10,15,20, 7]` and `[5,7]` are same\n        - In other words, if we have 2 prime numbers, then we are done, or if we have two co-primes we are good\n        - Is `[5,7]` is good - yes, why? `5 & 7 are co-prime` (that is `gcd = 1`)\n        - Is `[3,4]` is good - yes, why? `3 & 4 are co-prime` (that is `gcd = 1`)\n        - Is `[10,8]` is good - No, why? `10 & 8 are Not co-prime`, because they have a prime number `2` as common factor (that is `gcd = 2`)\n- So can I stop going ahead once I found 2 co-primes? yes\n  - `[8,9,100,200,300,400,500,600]` is same as `[8,9]`, as 8 & 9 are co-prime we don\'t need to look at `100, 200..`\n  - [9,100,200,300,400,500,600] is same as `[9,100]` yes they are `3*3` and `2*2*5*5` but there are no common factors with each other (`co-prime`), their only common factor is `1` (`gcd=1`), (`gcf=hcf=gcd=1`)\n    - So we can exit as soon as we find `two co-primes` (`gcd=1`)\n      - see last solution below for early exit\n- Why is `[6,10,15]` a kind of special test case?\n    - But `6*1 + 10*-2 + 15*1 = 1`\n    - gcd of 6, 10, and 15 is 1\n    - but there are no `co-primes`\n      - `co-primes` if present then good, but may not present too but good array for our question\n      - so `gcd is 1` can be trusted always, use and `co-primes` existence can be used for early exit\n- Want more? :)\n  - Check gcd properties here - https://en.wikipedia.org/wiki/Greatest_common_divisor#Properties\n    - Especially, see the closest one - 2nd property in above link - `B\xE9zout\'s identity`\n\nHope it is simple to understand.\n\n---\n\n```\nvar isGoodArray = function (A) {\n    const gcd = (a, b) => (b ? gcd(b, a % b) : a);\n    return A.reduce((g, n) => gcd(g, n)) === 1;\n};\n```\n\n![image](https://assets.leetcode.com/users/images/78b5db46-0a7e-4363-8dcc-c8a64de61bcc_1625144278.6591823.png)\n\n---\n\n```\nvar isGoodArray = function (A) {\n    return A.reduce((gcd = (a, b) => (b ? gcd(b, a % b) : a))) === 1;\n};\n```\n\n![image](https://assets.leetcode.com/users/images/c3f41dd7-ca8a-4da5-9663-5b428cb47bbd_1625144313.7914488.png)\n\n---\n\n```\nvar isGoodArray = (A) => A.reduce((gcd = (a, b) => (b ? gcd(b, a % b) : a))) === 1;\n```\n\n![image](https://assets.leetcode.com/users/images/93ab86ee-88be-4323-8f1a-6c8ac1e948ba_1625144355.069614.png)\n\n---\n\n```\nvar isGoodArray = function (A) {\n    const gcd = (a, b) => (b ? gcd(b, a % b) : a);\n\n    let g = A[0];\n    for (let n of A) {\n        g = gcd(g, n);\n        if (g === 1)\n            return true;    // early exit\n    }\n    return false;\n};\n```\n\n![image](https://assets.leetcode.com/users/images/aafe287e-a5ce-43e1-be5a-86fd66a49161_1625146895.2639222.png)\n\n---\n
['JavaScript']