Sherlock and GCD

Sherlock is stuck while solving a problem: Given an array , he wants to know if there exists a subset  of this array that follows these statements:

•  is a non-empty subset.
• There exists no integer  which divides all elements of B.
• There are no elements of B which are equal to another.

Example:

Input: n = 3, a = {1, 2, 3}
Output: YES

Approach

Java

public class SherlockAndGCD {
    public static void main(String[] args) {

        int n = 3;
        int[] a = { 1, 2, 3 };

        System.out.println(solve(a));

    }

    static int GCD(int a, int b) {
        if (b == 0)
            return a;
        return GCD(b, a % b);
    }

    static String solve(int[] a) {
        int n = a.length;
        int gcd = a[0];
        for (int i = 1; i < n; i++) {
            gcd = GCD(a[i], gcd);
        }
        if (gcd == 1 || gcd == 0)
            return "YES";
        else
            return "NO";
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

string solve(vector<int> a)
{
    int n = a.size();
    int gcd = a[0];
    for (int i = 1; i < n; i++)
    {
        gcd = __gcd(a[i], gcd);
    }
    if (gcd == 1 || gcd == 0)
        return "YES";
    else
        return "NO";
}

int main()
{

    int n = 3;
    vector<int> a = {1, 2, 3};

    cout << solve(a) << "\n";
    return 0;
}