1250. | OPTIMISED CODE | BEATS 94% | UNDERSTAND THE INTUITION
Intuition\n\n## Problem Statement\n\nLet\'s say I have an array {a1,a2,a3}. Now we want to find out if there exists a subset that can yield us 1. This means, do
# Intuition\n\n## Problem Statement\n\nLet\'s say I have an array `{a1,a2,a3}`. Now we want to find out if there exists a subset that can yield us 1. This means, does the equation `a1x + a2y + a3z = 1` (where x, y, z are integers) have a solution? \n\n## Bezout\'s Theorem\n\nThere is a direct mathematical identity called Bezout\'s Theorem which states:\n\nFor integers a, b, there exist integers x, y such that `ax + by = gcd(a,b)`.\n\nWe can use this theorem to address our question. Specifically, `a1x + a2y + a3z = 1` is true if `gcd(a1, a2, a3) == 1`.\n\n## Solution Approach\n\nTherefore, all we need to do now is calculate the gcd of all the elements in the array and check if the gcd is 1 or not. If you want to understand how this method works, look for the proof of Bezout\'s theorem.\n\n### Intuition Example\n\nConsider the example array `{3, 6}`. Now,\n\n`3x + 6y = 1`\n\nSimplifying further,\n\n`3(x + 2y) = 1`\n\n`x + 2y = 1/3`\n\nIt\'s clear that there are no integer values of x and y that can satisfy `x + 2y = 1/3`.\n\n### Tip\n\nWhile iterating over the array and calculating the gcd, if we find that the gcd is 1 at any point, there\'s no need to continue iterating further.\n\n\n# Approach\n1. **Initialization:**\n   - Initialize `x` with the first element of `nums`. This assumes `nums` is non-empty.\n\n2. **Iterate through array:**\n   - Iterate through each `num` in `nums`.\n\n3. **Reduce `num` to 1:**\n   - Use a `while` loop to repeatedly compute the modulo (`temp = x % num`) and update `x` and `num` until `num` becomes 0. This effectively reduces `num` to the greatest common divisor (gcd) of `x` and `num`.\n\n4. **Check condition:**\n   - After the `while` loop, check if `x` equals 1 (`if (x == 1)`). If true, return `true` indicating there exists a number `x` such that all elements in `nums` can be reduced to 1.\n\n5. **Return false:**\n   - If the loop completes without finding `x` equal to 1 for any `num`, return `false`.\n\n\n# Complexity\n- Time complexity:\n$$O(n)$$ \n\n- Space complexity:\n $$O(1)$$ \n\n# Code\n```\nclass Solution {\n    public boolean isGoodArray(int[] nums) {\n\n        int x = nums[0] ;\n        int temp ;\n\n        for(int num : nums)\n        {\n            while(num > 0)\n            {\n                temp = x%num ;\n                x = num ;\n                num = temp ;\n            }\n            if(x == 1) return true ;\n        }\n\n        return false ;\n        \n    }\n}\n```
['Java']