Euclid's algorithm to find common factor, with proof
TLDR - The array is good if and only if the array\'s elements do not share a common factor. Use Eulcid\'s algorithm iteratively to find if there is a common fac
TLDR - The array is good if and only if the array\'s elements do not share a common factor. Use Eulcid\'s algorithm iteratively to find if there is a common factor or not.\n\n# Intuition\nThe first approach I thought about was bad.\n\nThe second approach followed from the realization that if all the numbers shared a common factor, the array would not be "good" since any combination of them would also share that factor. I then realized that if there was no common factor to all the elements, then the array must be good (a mathematical proof follows the code below). Thus the question "is the array good?" reduces to "is there no factor common to all the elements?"\n\n# Approach\nWe need to find if there is a common factor to all the elements. A variable `factor` keeps track of the largest factor common to all the elements up to the current point in iteration. `factor` is initialized to nums[0], then as we iterate through the array, we update it to be the greatest common factor between the old `factor` and the current array element using Euclid\'s algorithm. If at any point `factor` is 1, then there is no common factor between the previously inspected elements; Thus the array is good and we return `true`. Otherwise, there is a common factor, the array is not good, and we return `false`.\n\n# Complexity\n- Time complexity: $O(nlogm)$\n\nEuclid\'s algorithm is logarithmic in the size of the elements. Since this algorithm has to be run for every array element (in the worst case), the overall complexity is $O(nlogm)$, where $n$ and $m$ are the size and maximum of `nums`, respectively\n\n- Space complexity: $O(1)$\n\nOnly one variable is used.\n\n# Code\n```\nclass Solution {\npublic:\n    bool isGoodArray(vector<int>& nums) {\n        int factor = nums[0];\n        for(int num:nums){\n            factor = euclid_gcd(factor,num);\n            if(factor==1){\n                return true;\n            }\n        }\n        return false;\n    }\n\n    int euclid_gcd(int a, int b){\n        if(b<a){\n            int temp = a;\n            a=b;\n            b=temp;\n        }\n        if(b%a==0){\n            return a;\n        }\n        return euclid_gcd(b%a,a);\n    }\n};\n```\n# Proof\nSuppose there is a prime factor, $p$, common to all elements. Then any integer combination of these elements, $a\\cdot nums[0]+b\\cdot nums[1]+...$ will be divisible by $p$. Since one is not divisible by $p$, this means that this sum will never equal one, thus in this case the array is not "good". \n\nOn the other hand, suppose no such prime factor exists. First, a lemma:\n\nLemma: For any positive coprime integers $x$ and $y$, there are integers $j$ and $k$ such that $jx-ky=1$.\nProof: Let $x$ and $y$ be positive coprime integers, i.e. integers which share no common factors. Consider the sequence $x\\%y,2x\\%y,...(y-1)x\\%y$. Each member of this sequence can take on integer values from 1 to y-1. \nSuppose two members $ax\\%y$ and $bx\\%y$ are equal, with $0<b<a<y$. Then there exist integers $c$ and $d$ such that $ax-cy=bx-dy$, with $(a-b)x = (c-d)y$. But $a-b<y$, thus the least common multiple of $x$ and $y$ is less than $x\\cdot y$. But $x$ and $y$ are coprime, so their least common multiple is $x\\cdot y$. This is a contradiction. Thus all member of the sequence are unique.\nSince all $y-1$ members of the sequence are unique, and there are $y-1$ possible values for them to take, every value from $1$ to $y=1$ appears in the sequence. Thus there exists some integer $j$ such that $jx\\%y=1$. Therefore there is some integer $k$ such that $jx-ky=1$.\n\nNow, suppose there is no prime factor common to all the elements. If there is only one element, then that element must be one (otherwise any factor of that element would be common to "all the elements"), and then the array is good under the combination $1*1=1$. Otherwise, there is more than one element. Let $a=nums[0]$. Consider the subset $nums[1],nums[2], . . . nums[n-1]$, where $n$ is the size of nums. Call the greatest common factor of this subset $b$. If $b$ shares a prime factor with $a$, then that factor is shared between all of the elements of the subset and $a$, and is therefore common to all of the elements - contradicting the assumption. Therefore, $a$ and $b$ are coprime. $b$ can be built as an integer combination of the elements of the subset, via the following method- start with $c = nums[1]$. For each of the elements of the subset $nums[2], nums[3]. . . nums[n-1]$, set $d = nums[i]$. Now, at the beginning of the each step, $c$ and $d$ should be positive integer combinations of the subsets. (This is the case for the first step-  the inductive case will be proven below). Iteratively update $c$ and $d$ according to the steps of Euclid\'s algorithm, i.e. subtract the smaller number from the larger until one of them is 0. Since this alorithm involves iteratively taking differences of integer combinations of the subset, the resulting $c$ and $d$ are integer combinations of the subset, and the larger is greatest common factor to the original numbers. Set $c$ to the larger of these numbers. Since $c$ is the greatest common factor to $gcf(nums[1]. . . nums[i-1])$ and $nums[i]$, it is the greatest common factor to $nums[1]...nums[i]$. Once the process is complete, $c=gcf(nums[1]. ..nums[n-1])=b$, and $c$ is an integer combination of this subset. Therefore $b$ is an integer combination of the subset. By the above lemma and the fact that $a$ and $b$ are coprime, there is an integer combination of $a$ and $b$ which is equal to one. This combination of $a$ and $b$ is an integer combination of $nums[0]$ and an integer combination of $nums[1]...nums[n-1]$, and therefore and integer combination of $nums[0]...nums[n-1]$. Therefore, there is an integer combination of $nums$ which is equal to one, and therefore the array is good.\n\nThus, the array is good if and only if there is no prime factor common to all elements.
['C++']