Check If A Subset Exists

Consider the array [2,7,14] and the subset [2,7]. Here, we can multiply 2 with 4 and 7 with -1, and we can add the modified elements present in the subset to obtain 1. Hence, the answer is 1 in this case.

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains a single integer, 'N', denoting the number of elements in the array. The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.

For each test case, print 1 - if the subset exists such that you can obtain 1 by multiplying all the elements in the subset by any arbitrary integer and adding all of them. Otherwise, print 0. Print the output of each test case in a separate line.

1 <= T <= 10 1 <= N <= 10^5 1 <= ARR[i] <= 10^9 Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, and 'ARR[i]' denotes the 'i' th element of the array 'ARR'. Time Limit: 1 sec

For the first test case, One of the possible subsets is [2,3]. We can multiply 2 with -4 and 3 with 3, and we can add the modified elements present in the subset to obtain 1. Hence, the answer is 1 in this case. For the second test case, No subset exists such that we can obtain 1 by multiplying all the elements in the subset by an integer and adding all elements present in the subset. Hence, the answer is 0 in this case.

For the first test case, One of the possible subsets is [3,5]. We can multiply 3 with 2 and 5 with -1, and we can add the modified elements present in the subset to obtain 1. Hence, the answer is 1 in this case. For the second test case, No subset exists such that we can obtain 1 by multiplying all the elements in the subset by an integer and adding all elements present in the subset. Hence, the answer is 0 in this case.

Bezout's identity

Bezout's identity states that, for any two non-zero integers a and b, let d be the greatest common divisor of a and b. Then there exist integral values of x and y such that the below equation holds true.

                           a*x + b*y = d

Now consider all subsets of ARR. We are trying to apply the same operations on a subset to obtain d as 1.We can generalize this identity for all subsets of ARR. Let d be the greatest common divisor of all elements present in the subset such that the below equation holds true.

               ARR[i]*x1 + ARR[j]*x2 + … + ARR[k]*xk  = d

Now consider the original problem, here our goal is to obtain d as 1. So, the greatest common divisor of all elements in the subset must be equal to 1. Our approach will be to find the greatest common divisor of all elements present in the subset, and we will check if the obtained greatest common divisor value is equal to 1, then we can obtain 1 by applying operations on the subset.

The greatest common divisor of 1 with any positive integer is 1. If there is a subset with the greatest common divisor of all elements equal to 1, then if you add more elements from ARR in that subset, the greatest common divisor of the subset will still remain 1. We can use this idea and find the greatest common divisor of all elements present in the array. We will check whether the greatest common divisor of all the elements that are present in the array is 1. If it is 1, then a possible subset exists, and we will return 1. Otherwise, we will return 0.

Algorithm:

We will initialize the variable gcdValue with ARR[0], and it will store the greatest common divisor of all elements present in the array.
Iterate start from 1 to N-1,
- Update gcdValue with the greatest common divisor of gcdValue and ARR[start].
Check if gcdValue is equal to 1
- A subset exists by which we can obtain 1 by applying operations on the subset. Hence, return 1.
Otherwise, if gcdValue is not equal to 1
- No possible subset exists by which we can obtain 1 by applying operations on the subset. Hence, return 0.

Time Complexity

O(N*Log(Min(ARR))), where N is the number of elements in the array.

We are traversing through the array ARR, and in each iteration, it takes O(Log(Min(ARR))) time to find the greatest common divisor. Hence the overall time complexity is O(N*Log(Min(ARR))).

Space Complexity

O(1).

Constant space is being used. Hence, the overall Space Complexity is O(1).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation For Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation Of Sample Input 2: