Last Updated: 17 Apr, 2021

Check If A Subset Exists

Moderate

Asked in companies

Solve now

Problem statement

You are given an array ‘ARR’ of size ‘N’. Your task is to determine whether a subset of ‘ARR’ exists such that you can obtain 1 by multiplying all the elements in the subset by any arbitrary integer (can be different for different elements) and adding all of them.

Subset of an array 'ARR' is a tuple that can be obtained from 'ARR' by removing some (possibly all) elements of 'ARR'.

For example:

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.

Input Format:

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'.

Output Format:

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.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

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

Solve now

Approaches

01 Approach

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.

Solve now