Given a set of n numbers. The task is to count all the subsets of the given set which only have even numbers and all are distinct.
Note: By the property of sets, if two subsets have the same set of elements then they are considered as one. For example: [2, 4, 8] and [4, 2, 8] are considered to be the same.
 
Example 1:
Input : 
n = 8
a[] = {4, 2, 1, 9, 2, 6, 5, 3}
Output : 
7
Explanation:
The subsets are:
[4], [2], [6], [4, 2],
[2, 6], [4, 6], [4, 2, 6]
 
Example 2:
Input : 
n = 13
a[] = {10, 3, 4, 2, 4, 20, 10, 6, 8, 14, 2, 6, 9}
Output : 
127
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countSubsets() which takes the array a[] and its size n as inputs and returns the Count of possible subsets.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
 
Constraints:
1<=n<=10^{5}
1<=a[i]<=10^{3}
It is Guaranteed that answers will fit in 64-bits.

Source: geeksforgeeks | Difficulty: EASY
Tags: Combinatorics

Data structures

Mathematics

Starter code: #User function Template for python3



def countSubsets( a, n):

    # code here

    

    



Solutions:
def countSubsets(a, n):
	s = set()
	for x in a:
		if x % 2 == 0:
			s.add(x)
	count = len(s)
	ans = pow(2, count) - 1
	return ans


def countSubsets(a, n):
	setti = set()
	for item in a:
		if item % 2 == 0:
			setti.add(item)
	return 2 ** len(setti) - 1


def countSubsets(a, n):
	s = set()
	for i in a:
		if i % 2 == 0:
			s.add(i)
	n = len(s)
	return 2 ** n - 1


def countSubsets(a, n):
	even = []
	N = len(even)
	for number in a:
		if number % 2 == 0 and number not in even:
			even.append(number)
	return 2 ** len(even) - 1


def countSubsets(a, n):
	even = []
	c = 0
	for i in range(n):
		if a[i] % 2 == 0 and a[i] not in even:
			even.append(a[i])
			c += 1
	subset = 2 ** c - 1
	return subset


def countSubsets(a, n):
	c = 0
	n = len(set(a))
	a = list(set(a))
	for i in range(n):
		if a[i] % 2 == 0:
			c += 1
	return 2 ** c - 1


def countSubsets(a, n):
	l = []
	c = 0
	for i in a:
		if i % 2 == 0 and i not in l:
			l.append(i)
			c += 1
	return (1 << c) - 1


def countSubsets(a, n):
	d = {}
	c = 0
	for i in a:
		if i not in d and i % 2 == 0:
			d[i] = 1
			c += 1
	return pow(2, c) - 1


def countSubsets(arr, n):
	ans = 0
	d = {}
	cnt = 1
	for i in range(n - 1, -1, -1):
		if arr[i] % 2 == 0 and arr[i] not in d:
			ans += cnt
			cnt = cnt << 1
			d[arr[i]] = True
	return ans


def countSubsets(a, n):
	cout = 0
	a = set(a)
	for i in a:
		if i % 2 == 0:
			cout += 1
	return 2 ** cout - 1


def countSubsets(a, n):
	a = set(a)
	lst = []
	for i in a:
		if i % 2 == 0:
			lst.append(i)
	b = len(lst)
	return 2 ** b - 1


def countSubsets(a, n):
	count = 0
	n = int(len(set(a)))
	a = list(set(a))
	for i in a:
		if i % 2 == 0:
			count += 1
	return 2 ** count - 1


def countSubsets(a, n):
	s = set([x for x in a if x % 2 == 0])
	return pow(2, len(s)) - 1


def countSubsets(a, n):
	even = []
	for i in range(n):
		if a[i] % 2 == 0 and a[i] not in even:
			even.append(a[i])
	l = len(even)
	return 2 ** l - 1


def countSubsets(a, n):
	c = 0
	d = {}
	for x in a:
		if x % 2 == 0:
			d[x] = 1
	r = len(d)
	return 2 ** r - 1


import math

def countSubsets(a, n):
	evennum = set()
	for tmp in a:
		if tmp % 2 == 0:
			evennum.add(tmp)
	return pow(2, len(evennum)) - 1

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(countSubsets(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def countSubsets(a, n):
	ans = 0
	s = set()
	for i in a:
		if i & 1 == 0:
			s.add(i)
	ans = (1 << len(s)) - 1
	return ans

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(countSubsets(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def countSubsets(a, n):
	cnt = 0
	n = int(len(set(a)))
	a = list(set(a))
	for i in range(n):
		if a[i] % 2 == 0:
			cnt += 1
	return 2 ** cnt - 1


def countSubsets(a, n):
	a_set = set(a)
	cnt = 0
	for i in a_set:
		if i % 2 == 0:
			cnt = cnt + 1
	return pow(2, cnt) - 1


def countSubsets(a, n):
	ar = set()
	for i in range(n):
		if a[i] % 2 == 0:
			ar.add(a[i])
	x = len(ar)
	res = pow(2, x) - 1
	return res


def countSubsets(a, n):
	tmp = set()
	for x in a:
		if x % 2 == 0:
			tmp.add(x)
	return (1 << len(tmp)) - 1


from math import factorial as f

def countSubsets(a, n):
	c = 0
	b = list(set(a))
	for j in range(len(b)):
		if b[j] % 2 == 0:
			c += 1
	s = 2 ** c - 1
	return s


def countSubsets(a, n):
	l = set(a)
	k = list(l)
	count = 0
	for i in k:
		if i % 2 == 0:
			count += 1
	return 2 ** count - 1


def countSubsets(a, n):
	s = set()
	cnt = 0
	for val in a:
		if val in s or val % 2 != 0:
			continue
		cnt += 1
		s.add(val)
	return 2 ** cnt - 1