Check If an Array Can Produce Sum of 1 Using Linear Combinations
Intuition\nThe problem requires checking if you can create a sum of 1 using any subset of given integers, each of which can be multiplied by any integer. The co
# Intuition\nThe problem requires checking if you can create a sum of `1` using any subset of given integers, each of which can be multiplied by any integer. The core idea relies on number theory. Specifically, if you can express `1` as a combination of the numbers in the array, then their greatest common divisor (GCD) must be `1`. This is because the GCD of a set of numbers is the smallest positive integer that can be expressed as a linear combination of those numbers. Therefore, if the GCD is `1`, it means that `1` can be expressed using some combination of those numbers.\n# Approach\n1. Compute the GCD:\n\n- Calculate the GCD of all numbers in the array. This can be done iteratively using the `std::gcd` function from the C++ Standard Library.\n- If at any point during the GCD calculation, the GCD becomes `1`, we can immediately conclude that the array is good because `1` can be expressed as a linear combination of these numbers.\n\n2. Early Exit:\n\n- As soon as the GCD becomes `1`, we can exit early, optimizing the solution by avoiding further unnecessary calculations.\n\n3. Final Check:\n\n- If the final GCD after processing all elements is `1`, then return `true`. Otherwise, return `false`.\n# Complexity\n- Time complexity: `O(n)`\n    - The time complexity is `O(n)` because we traverse the array once and compute the GCD in each iteration. The `std::gcd` function operates in logarithmic time relative to the values involved, making the overall complexity linear with respect to the number of elements.\n- Space complexity: `O(1)`\nThe space complexity is `O(1)` because we use only a few extra variables for storing the GCD value and iterating through the array.\n# Code\n```\n#include <vector>\n#include <algorithm> // for std::gcd\n\nclass Solution {\npublic:\n    bool isGoodArray(std::vector<int>& nums) {\n        int gcd_value = nums[0];\n        \n        // Compute the GCD of the entire array\n        for (int num : nums) {\n            gcd_value = std::gcd(gcd_value, num);\n            if (gcd_value == 1) {\n                return true; // Early exit if GCD becomes 1\n            }\n        }\n        \n        // Final check if GCD is 1\n        return gcd_value == 1;\n    }\n};\n\n```
['Array', 'Math', 'Number Theory', 'C++']