Elena is the topper of the class. Once her teacher asked her a problem. He gave Elena an array of integers of length n. He calls a subset of array arr good if its product can be represented as a product of one or more distinct prime numbers. He asked her to find the number of different good subsets in arr modulo 10^{9} + 7.
As a good friend of Elena help her to solve the problem.
Example 1:
Input:
N: 4
arr: {1,2,3,4}
Output: 6
Explanation: 
The good subsets are:
- [1,2]: product is 2, which is the product of distinct
prime 2.
- [1,2,3]: product is 6, which is the product of 
distinct primes 2 and 3.
- [1,3]: product is 3, which is the product of distinct
prime 3.
- [2]: product is 2, which is the product of distinct
 prime 2.
- [2,3]: product is 6, which is the product of distinct
primes 2 and 3.
- [3]: product is 3, which is the product of distinct
prime 3.
Example 2:
Input:
N : 3
arr : {2, 2, 3}
Output: 5
Explanantion:
The good subsets are : {2}, {2}, {2, 3}, {2, 3}, {3}
Your Task:
The task is to complete the function goodSubsets() which takes an integer n and an array arr as the input parameters and should return the number of different good subsets.
Expected Time Complexity: O(NlogN)
Expected Space Complexity: O(N)
Constraints:
	1 <= N <= 10^{5}
	1< = arr[i] <= 30

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Bit manipulation

Data structures

Starter code: from typing import List





class Solution:

    def goodSubsets(self, n : int, arr : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		from functools import reduce
		MOD = 10 ** 9 + 7
		primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
		A = [0] * 31
		for v in arr:
			A[v] += 1

		def exc(*ex):
			return [v for v in primes if v not in ex and A[v] > 0]
		mp = {(6,): exc(2, 3), (10,): exc(2, 5), (14,): exc(2, 7), (15,): exc(3, 5), (15, 14): exc(2, 3, 5, 7), (21,): exc(3, 7), (21, 10): exc(2, 3, 5, 7), (22,): exc(2, 11), (22, 15): exc(2, 3, 5, 11), (22, 21): exc(2, 3, 7, 11), (26,): exc(2, 13), (26, 15): exc(2, 3, 5, 13), (26, 21): exc(2, 3, 7, 13), (30,): exc(2, 3, 5)}
		ans = 0
		for v in primes:
			ans = (ans + A[v] * (1 + ans)) % MOD
		for (cvs, targets) in mp.items():
			if any((A[v] == 0 for v in cvs)):
				continue
			prod = reduce(lambda a, b: a * b % MOD, (A[v] for v in cvs))
			tmp = 0
			for v in targets:
				tmp = (tmp + A[v] * (1 + tmp)) % MOD
			ans = (ans + (tmp + 1) * prod) % MOD
		K1 = pow(2, A[1], MOD)
		ans = ans * K1 % MOD
		return ans


from typing import List

class Solution:

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		mod = int(1000000000.0) + 7
		maskPrime = [0] * 31
		primeNumbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
		for i in range(2, 31):
			if i % 4 == 0 or i % 9 == 0 or i == 25:
				continue
			mask = 0
			for j in range(10):
				if i % primeNumbers[j] == 0:
					mask |= 1 << j
			maskPrime[i] = mask

		def powerOfTwo(n):
			(result, value) = (1, 2)
			while n != 0:
				if n & 1 == 1:
					result = result * value % mod
				value = value * value % mod
				n >>= 1
			return result
		(oneCount, count, dp) = (0, [0] * 31, [0] * 1024)
		dp[0] = 1
		for element in arr:
			if element == 1:
				oneCount += 1
			elif maskPrime[element] != 0:
				count[element] += 1
		for i in range(31):
			if count[i] == 0:
				continue
			for j in range(1024):
				if j & maskPrime[i] != 0:
					continue
				dp[j | maskPrime[i]] = (dp[j | maskPrime[i]] + dp[j] * count[i]) % mod
		answer = sum(dp) % mod - 1
		if oneCount != 0:
			answer = answer * powerOfTwo(oneCount) % mod
		return answer


from typing import List

class Solution:

	def __init__(self):
		self.mod = int(1000000000.0 + 7)
		self.mp = [0] * 31
		primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
		for i in range(2, 31):
			if i % 4 == 0 or i % 9 == 0 or i == 25:
				continue
			mask = 0
			for j in range(10):
				if i % primes[j] == 0:
					mask |= 1 << j
			self.mp[i] = mask

	def pow(self, n: int) -> int:
		(ans, m) = (1, 2)
		while n != 0:
			if n & 1 == 1:
				ans = ans * m % self.mod
			m = m * m % self.mod
			n >>= 1
		return ans

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		one = 0
		dp = [0] * 1024
		cnt = [0] * 31
		dp[0] = 1
		for i in arr:
			if i == 1:
				one += 1
			elif self.mp[i] != 0:
				cnt[i] += 1
		for i in range(31):
			if cnt[i] == 0:
				continue
			for j in range(1024):
				if j & self.mp[i] != 0:
					continue
				dp[j | self.mp[i]] = (dp[j | self.mp[i]] + dp[j] * cnt[i]) % self.mod
		ans = sum(dp) % self.mod - 1
		if one != 0:
			ans = ans * self.pow(one) % self.mod
		return ans


from typing import List, Dict
from collections import Counter
distinct_factors = {2: [2], 3: [3], 5: [5], 6: [2, 3], 7: [7], 10: [2, 5], 11: [11], 13: [13], 14: [2, 7], 15: [3, 5], 17: [17], 19: [19], 21: [3, 7], 22: [2, 11], 23: [23], 26: [2, 13], 29: [29], 30: [2, 3, 5]}
primes_to_idx = {2: 0, 3: 1, 5: 2, 7: 3, 11: 4, 13: 5, 17: 6, 19: 7, 23: 8, 29: 9}
MOD = 10 ** 9 + 7

class Solution:

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		usable_nums = []
		num_ones = 0
		for i in range(n):
			a = arr[i]
			if a > 30:
				raise Exception('Found term outside of expected range: ' + str(a))
			if a in distinct_factors:
				usable_nums.append(a)
			if a == 1:
				num_ones += 1
		divisibility_groups = [Counter() for p in primes_to_idx]
		for a in usable_nums:
			for factor in distinct_factors[a]:
				div_group = divisibility_groups[primes_to_idx[factor]]
				div_group[a] += 1
		count_wo_ones = count_good_subsets(divisibility_groups) - 1
		one_multiplier = pow(2, num_ones, MOD)
		total_count = count_wo_ones * one_multiplier % MOD
		return total_count

def count_good_subsets(divisibility_groups: List[Dict[int, int]], depth=0):
	chosen_div_group = get_first_nonempty_group(divisibility_groups)
	if chosen_div_group is None:
		return 1
	(chosen_num, chosen_count) = get_an_element(chosen_div_group)
	cur_count = 0
	div_groups_for_chosen = [primes_to_idx[factor] for factor in distinct_factors[chosen_num]]
	removed_nums = {}
	for div_group_idx in div_groups_for_chosen:
		div_group = divisibility_groups[div_group_idx]
		assert chosen_num in div_group
		del div_group[chosen_num]
		for neighbor_num in list(div_group.keys()):
			neighbor_count = remove_from_all_div_groups(neighbor_num, divisibility_groups)
			if neighbor_count is not None:
				removed_nums[neighbor_num] = neighbor_count
	assert chosen_num not in removed_nums
	count_less_cur_div_groups = count_good_subsets(divisibility_groups, depth + 1)
	cur_count = count_less_cur_div_groups * chosen_count % MOD
	for (num, count) in removed_nums.items():
		add_to_all_div_groups(num, count, divisibility_groups)
	count_ignoring_chosen = count_good_subsets(divisibility_groups, depth + 1)
	cur_count = (cur_count + count_ignoring_chosen) % MOD
	add_to_all_div_groups(chosen_num, chosen_count, divisibility_groups)
	return cur_count

def remove_from_all_div_groups(num, divisibility_groups):
	div_groups_for_num = (primes_to_idx[factor] for factor in distinct_factors[num])
	count = None
	for div_group_idx in div_groups_for_num:
		div_group = divisibility_groups[div_group_idx]
		if num in div_group:
			count = div_group[num]
			del div_group[num]
	return count

def add_to_all_div_groups(num, count, divisibility_groups):
	div_groups_for_num = (primes_to_idx[factor] for factor in distinct_factors[num])
	for div_group_idx in div_groups_for_num:
		div_group = divisibility_groups[div_group_idx]
		div_group[num] = count

def get_first_nonempty_group(div_groups):
	for group in div_groups:
		if len(group) > 0:
			return group
	return None

def get_an_element(d: Dict[int, int]):
	for (k, v) in d.items():
		return (k, v)
	return None


from typing import List

class Solution:

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		mod = 10 ** 9 + 7
		prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
		arr1 = [0] * 31
		for i in range(2, 31):
			m = 0
			if i % 4 == 0 or i % 9 == 0 or i == 25:
				arr1[i] = m
				continue
			for j in range(len(prime)):
				if i % prime[j] == 0:
					m |= 1 << j
			arr1[i] = m
		dp = [0 for _ in range(1 << 10)]
		dp[0] = 1
		primecount = [0] * 32
		o = 0
		for i in arr:
			if i == 1:
				o += 1
			elif arr1[i] != 0:
				primecount[i] += 1
		for i in range(31):
			if primecount[i] == 0:
				continue
			for j in range(0, 1 << 10):
				if j & arr1[i] != 0:
					continue
				dp[j | arr1[i]] = (dp[j | arr1[i]] + dp[j] * primecount[i]) % mod
		ans = 0
		for i in dp:
			ans = (ans + i) % mod
		ans -= 1
		if o != 0:
			ans = ans * pow(2, o, mod) % mod
		return ans


from typing import List
from collections import Counter
from functools import lru_cache

class Solution:

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
		count = Counter(arr)
		MOD = 10 ** 9 + 7
		dp = [1 for j in range(1 << 10)]
		for num in count:
			if num == 1 or num == 25 or num % 4 == 0 or (num % 9 == 0):
				continue
			mask = sum((1 << ind for (ind, p) in enumerate(primes) if num % p == 0))
			for j in range((1 << 10) - 1, -1, -1):
				if mask | j == j:
					dp[j] = (dp[j] + dp[mask ^ j] * count[num]) % MOD
		return (dp[1023] - 1) * pow(2, count[1], MOD) % MOD


mod = 10 ** 9 + 7
mapper = [0] * 31
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
for i in range(2, 31):
	if 0 == i % 4 or 0 == i % 9 or 25 == i:
		continue
	mask = 0
	for j in range(10):
		if 0 == i % prime[j]:
			mask |= 1 << j
		mapper[i] = mask

class Solution:

	def goodSubsets(self, n, arr):
		one = 0
		dp = [0] * 1024
		cnt = [0] * 31
		dp[0] = 1
		for i in arr:
			if i == 1:
				one += 1
			elif mapper[i] != 0:
				cnt[i] += 1
		for i in range(31):
			if cnt[i] == 0:
				continue
			for j in range(1024):
				if 0 != j & mapper[i]:
					continue
				dp[j | mapper[i]] = (dp[j | mapper[i]] + dp[j] * cnt[i]) % mod
		res = 0
		for i in dp:
			res = (res + i) % mod
		res -= 1
		if one != 0:
			res = res * pow(2, one, mod) % mod
		return res


from typing import List
from collections import *

class Solution:

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		d = dict()
		prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
		for i in range(len(prime)):
			d[prime[i]] = i
		mod = 10 ** 9 + 7
		p = 30

		def mmul(a, b):
			a = a % mod
			b = b % mod
			return (a * b % mod + mod) % mod

		def madd(a, b):
			a = a % mod
			b = b % mod
			return ((a + b) % mod + mod) % mod

		def msub(a, b):
			a = a % mod
			b = b % mod
			return ((a - b) % mod + mod) % mod

		def go(ind, mask):
			if ind == x:
				return 1
			if d1[ind, mask] != 0:
				return d1[ind, mask]
			c1 = go(ind + 1, mask)
			fl = 0
			ori = mask
			c2 = 0
			q = arr[ind]
			for i in prime:
				while q % i == 0:
					if 2 ** d[i] & ori != 0:
						fl = 1
						break
					else:
						ori ^= 2 ** d[i]
					q = q // i
			if fl == 0:
				c2 = mmul(fre[arr[ind]], go(ind + 1, ori))
			ans = madd(c1, c2)
			d1[ind, mask] = ans
			return ans
		fre = [0] * 31
		for i in arr:
			fre[i] += 1
		arr = list(set(arr))
		x = len(arr)
		d1 = defaultdict(int)
		return msub(msub(go(0, 0), 1), arr.count(1))


from typing import List

class Solution:

	def goodSubsets(self, n: int, arr: List[int]) -> int:
		from operator import mul
		from functools import reduce
		MOD = 10 ** 9 + 7
		primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
		A = [0] * 31
		for v in arr:
			A[v] += 1
		K1 = pow(2, A[1], MOD)
		tmp = K1
		for pv in primes:
			tmp = tmp * (A[pv] + 1) % MOD
		ans = (tmp - K1) % MOD

		def exc(*ex):
			return [v for v in primes if v not in ex and A[v] > 0]
		mp = {(6,): exc(2, 3), (10,): exc(2, 5), (14,): exc(2, 7), (15,): exc(3, 5), (15, 14): exc(2, 3, 5, 7), (21,): exc(3, 7), (21, 10): exc(2, 3, 5, 7), (22,): exc(2, 11), (22, 15): exc(2, 3, 5, 11), (22, 21): exc(2, 3, 7, 11), (26,): exc(2, 13), (26, 15): exc(2, 3, 5, 13), (26, 21): exc(2, 3, 7, 13), (30,): exc(2, 3, 5)}
		for (cvs, targets) in mp.items():
			prod_comp = reduce(mul, (A[v] for v in cvs))
			if prod_comp == 0:
				continue
			MUL = K1 * prod_comp % MOD
			su = 0
			for mask in range(2 ** len(targets)):
				(tmp, i) = (1, 0)
				while mask:
					if mask & 1:
						tmp = tmp * A[targets[i]] % MOD
					i += 1
					mask >>= 1
				su = (su + tmp) % MOD
			ans = (ans + MUL * su) % MOD
		return ans