1250.check if it is a good array

Description Link to heading

Solution Link to heading

Actually, what we need to determine is whether the maximum common divisor of all elements in the array is 1.

We can use rolling division to get the maximum common divisor gcd of nums[0] and nums[1], then get the new maximum common divisor gcd of gcd and nums[2]…

Code Link to heading

#include <vector>
using std::vector;
class Solution {
  public:
    int gcd(int a, int b) {
        // b^=a,a^=b,b^=a the same as swap(a, b)
        while (b ^= (a ^= (b ^= (a %= b))))
            ;
        return a;
    }
    bool isGoodArray(vector<int> &nums) {
        if (nums.size() == 1)
            return nums[0] == 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            int tmp = gcd(nums[i], nums[i + 1]);
            if (tmp == 1) // gcd is 1
                return true;
            nums[i + 1] = tmp;
        }
        return true;
    }
};