Simple C++ with Explanation
According to Euclid\'s Theorem,\nIf the GCD of two integers (a,b) is d, then there exists two integers x and y such that ax + by = d.\n\nIf a,b,c... are the ele
According to Euclid\'s Theorem,\n***If the GCD of two integers (a,b) is d, then there exists two integers x and y such that ax + by = d.***\n\nIf a,b,c... are the elements of the array we are calculating ax + by + cz...which gives hint that we have to use the above theorem.\n\nNow in this problem the d is given to be 1, which means the GCD should be 1.\nSo instead of checking for all posiible subsets of the given array it is enough to check every pair (a,b).\n***"Does the array contain two integers a and b such that ax + by = 1 for some integers x,y ?"***\nOr the same question can be asked as\n***"Does the array contain two co-prime integers?"***\n\nBut checking all pairs will have quadratic time complexity. We have to optimize it.\n\nNow what happens if we calculate the GCD of all the integers in the array ?\nIf the array contains co-prime integers then the GCD of those two will become 1 and the GCD of 1 with the remaining n-2 integers will be 1 only.\nBut if the array does not contain coprime integers then the GCD of all the integers will be greater than 1.\n\nSo the question reduces to\n***"Is the GCD of all the number in the array equal to 1?"***\n```\nclass Solution {\npublic:\n    bool isGoodArray(vector<int>& nums)\n    {\n        int GCD = nums[0];\n        \n        for (int i = 1; i < nums.size(); i++)\n        {\n            GCD = __gcd(GCD, nums[i]);\n        }\n        \n        return GCD == 1;\n    }\n};\n```
[]