Given is an array A[] of size N. Return the number of non-empty subsequences such that the product of all numbers in the subsequence is Power of 2. Since the answer may be too large, return it modulo 10^{9} + 7.
Example 1:
Input:
N = 3
A[] = {1, 6, 2}
Output:
3
Explanation:
The subsequence that 
can be chosen is {1},
{2} and {1,2}.
Example 2:
Input:
N = 3
A[] = {3, 5, 7}
Output:
0
Explanation:
No subsequences exist.
Your Task:
You don't need to read input or print anything. Your task is to complete the function numberOfSubsequences() which takes an integer N and an array A and returns the number of subsequences that exist. As this number can be very large return the result under modulo 10^{9}+7.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= A[i] <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def numberOfSubsequences (ob,N,A):

        # code here 

Solutions:
class Solution:

	def numberOfSubsequences(ob, N, A):
		count = 0
		for item in A:
			count += bin(item).count('1') == 1
		return (2 ** count - 1) % (10 ** 9 + 7)


class Solution:

	def numberOfSubsequences(ob, N, A):
		mod = 10 ** 9 + 7
		factor_2 = sum([1 for x in A if x and (not x & x - 1)])
		result = 2 ** factor_2
		return (result % mod - 1) % mod


class Solution:

	def is2pow(self, n):
		return n and (not n & n - 1)

	def numberOfSubsequences(self, N, A):
		mod = 1000000007
		count = 0
		for i in A:
			if self.is2pow(i):
				count += 1
		return pow(2, count, mod) - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		for i in A:
			if i and (not i & i - 1):
				c += 1
		return ((1 << c) - 1) % 1000000007


class Solution:

	def numberOfSubsequences(ob, N, A):

		def helper(x):
			return x and (not x & x - 1)
		count = 0
		for i in A:
			if helper(i):
				count += 1
		return pow(2, count, 1000000007) - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		for i in range(N):
			b = bin(A[i])[2:]
			co = b.count('0')
			if co == len(b) - 1 and b[0] == '1':
				c += 1
		return (2 ** c - 1) % 1000000007


class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		for i in A:
			if i & i - 1 == 0:
				c += 1
		return (2 ** c - 1) % 1000000007


class Solution:

	def isPower2(self, n):
		return n & n - 1 == 0

	def numberOfSubsequences(self, N, A):
		count = 0
		for x in A:
			count += self.isPower2(x)
		return ((1 << count) - 1) % (10 ** 9 + 7)


class Solution:

	def numberOfSubsequences(ob, N, A):
		import math
		A2 = []
		for i in A:
			if math.ceil(math.log(i, 2)) == math.floor(math.log(i, 2)):
				A2.append(i)
		n = len(A2)
		return (2 ** n - 1) % (10 ** 9 + 7)


class Solution:

	def numberOfSubsequences(self, N, A):
		count = 0
		for i in range(N):
			if A[i] & A[i] - 1 == 0:
				count += 1
		return (2 ** count - 1) % (10 ** 9 + 7)


class Solution:

	def numberOfSubsequences(ob, N, A):
		s = set()
		toadd = 1
		for i in range(33):
			toadd = 1 << i
			s.add(toadd)
		count = 0
		for i in A:
			if i in s:
				count += 1
		return (1 << count) % 1000000007 - 1


class Solution:

	def numberOfSubsequences(ob, N, A):

		def isPowerOf2(num):
			if num == 0:
				return False
			if num == 1:
				return True
			if num & num - 1:
				return False
			return True

		def powm(a, b, mod):
			res = 1
			while b:
				if b & 1:
					res = res * a % mod
				a = a * a % mod
				b >>= 1
			return res
		count = 0
		for i in range(N):
			if isPowerOf2(A[i]):
				count += 1
		return (powm(2, count, 1000000007) - 1 + 1000000007) % 1000000007


import math

class Solution:

	def numberOfSubsequences(ob, N, A):

		def Log2(x):
			return math.log10(x) / math.log10(2)

		def isPowerOfTwo(n):
			if n == 0:
				return False
			return math.ceil(Log2(n)) == math.floor(Log2(n))
		mod = pow(10, 9) + 7
		sum1 = 0
		count = 0
		for i in range(N):
			if isPowerOfTwo(A[i]):
				count += 1
		return (pow(2, count) - 1) % mod


class Solution:

	def numberOfSubsequences(ob, N, A):
		cnt = 0
		for a in A:
			if a & a - 1 == 0:
				cnt += 1
		return (2 ** cnt - 1) % (10 ** 9 + 7)


import math

class Solution:

	def numberOfSubsequences(self, n, a):
		mod = 10 ** 9 + 7
		count = 0
		for i in a:
			if math.log(i, 2) - int(math.log(i, 2)) == 0:
				count += 1
		return pow(2, count, mod) - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		cnt = 0
		for i in range(N):
			if A[i] & A[i] - 1 == 0:
				cnt += 1
		return (2 ** cnt - 1) % 1000000007


class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		for i in range(N):
			val = A[i]
			if val & val - 1 == 0:
				c += 1
		MOD = int(1000000000.0 + 7)
		ans = 1
		a = 2
		while c:
			if c & 1:
				ans *= a
				ans %= MOD
			a = a * a
			a %= MOD
			c >>= 1
		return ans - 1


class Solution:
	modulo = 10 ** 9 + 7

	def numberOfSubsequences(self, N, A):
		power_2_count = 0
		for i in range(N):
			if A[i] & A[i] - 1 == 0:
				power_2_count += 1
		ans = 0
		tmp_ans = 1
		choose_i = 1
		while power_2_count > 0:
			tmp_ans = tmp_ans * power_2_count // choose_i
			ans += tmp_ans
			power_2_count -= 1
			choose_i += 1
		return ans % self.modulo


class Solution:

	def numberOfSubsequences(ob, N, A):
		mod = 1000000007
		c = 0
		lst = []
		for i in range(28):
			lst.append(2 ** i)
		for i in range(N):
			if A[i] in lst:
				c += 1
		return (2 ** c - 1) % mod


class Solution:

	def solve(ob, n):
		return n > 0 and n & n - 1 == 0

	def numberOfSubsequences(ob, n, a):
		c = 0
		mod = 10 ** 9 + 7
		for i in range(n):
			if ob.solve(a[i]):
				c += 1
		return pow(2, c, mod) - 1


def p2(n):
	return n and (not n & n - 1)

class Solution:

	def numberOfSubsequences(ob, N, A):
		k = len([v for v in A if p2(v)])
		m = 1000000007
		return pow(2, k, m) - 1


from itertools import combinations
import math

class Solution:

	def numberOfSubsequences(ob, N, A):
		count = 0
		for i in A:
			if str(math.log10(i) / math.log10(2))[-1] == '0':
				count += 1
		return (2 ** count - 1) % 1000000007


MOD = 10 ** 9 + 7

class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		for i in range(N):
			if A[i] & A[i] - 1 == 0:
				c += 1
		return pow(2, c, MOD) - 1


import math

def is_pow_of_2(n):
	if n & n - 1 == 0:
		return True
	return False
	for i in range(32):
		if n == 1 << i:
			return True
	return False

class Solution:

	def numberOfSubsequences(ob, N, A):
		pow_of_2_elms_cnt = 0
		for i in range(N):
			if is_pow_of_2(A[i]):
				pow_of_2_elms_cnt += 1
		res = 0
		comb_tot_fact = math.factorial(pow_of_2_elms_cnt)
		comb_elem_fact = 1
		comb_tot_min_elem_fact = comb_tot_fact
		for i in range(1, pow_of_2_elms_cnt + 1):
			comb_elem_fact *= i
			comb_tot_min_elem_fact //= pow_of_2_elms_cnt - i + 1
			res += comb_tot_fact // (comb_elem_fact * comb_tot_min_elem_fact)
		return res % 1000000007


class Solution:

	def numberOfSubsequences(ob, N, A):
		count_2 = 0
		for i in range(len(A)):
			if A[i] & A[i] - 1 == 0:
				count_2 += 1
		ans = 2 ** count_2 - 1
		return ans % (10 ** 9 + 7)


class Solution:

	def numberOfSubsequences(ob, n, a):
		sub = []
		for i in range(n):
			if a[i] & a[i] - 1 == 0:
				sub.append(a[i])
		c = len(sub)
		l = 2 ** c - 1
		return l % 1000000007


class Solution:

	def numberOfSubsequences(ob, n, arr):
		count = 0
		mod = 10 ** 9 + 7
		for (i, ele) in enumerate(arr):
			if ele and ele & ele - 1 == 0:
				count += 1
		return ((1 << count) - 1) % mod


class Solution:

	def isp(ob, n: int) -> bool:
		d = True
		if n == 1:
			return True
		elif n == 0:
			return False
		elif n < 0:
			return False
		while n != 1:
			if n % 2 == 0:
				d = True
			else:
				return False
			n = int(n / 2)
		return d

	def numberOfSubsequences(ob, N, A):
		cnt = 0
		for i in range(N):
			if ob.isp(A[i]):
				cnt += 1
		return (2 ** cnt - 1) % 1000000007


import math

class Solution:

	def isPower(n):
		return n and (not n & n - 1)

	def numberOfSubsequences(ob, N, A):
		m = 10 ** 9 + 7
		count = 0
		ans = 1
		for i in range(N):
			if A[i] == 1 or Solution.isPower(A[i]):
				count += 1
		return pow(2, count, m) - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		mod = 1000000007
		cnt = 0
		for x in A:
			if x and (not x & x - 1):
				cnt += 1
		return pow(2, cnt, mod) - 1


class Solution:

	def numberOfSubsequences(ob, n, arr):

		def is2pow(n):
			return n and (not n & n - 1)
		mod = 1000000007
		count = 0
		for i in A:
			if is2pow(i):
				count += 1
		return pow(2, count, mod) - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		mod = 10 ** 9 + 7
		count = 0
		for i in A:
			if i and (not i & i - 1):
				count += 1
		return pow(2, count, mod) - 1


import math

def Log2(x):
	if x == 0:
		return false
	return math.log10(x) / math.log10(2)

def isp(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))

class Solution:

	def numberOfSubsequences(ob, N, A):
		lst = []
		for i in range(len(A)):
			if isp(A[i]):
				lst.append(A[i])
		if len(lst) == 0:
			return 0
		return pow(2, len(lst)) % 1000000007 - 1


import math

class Solution:

	def numberOfSubsequences(ob, N, A):
		mod = 1000000007
		count = 0
		for i in range(N):
			temp = math.log2(A[i])
			if int(temp) == math.ceil(temp):
				count += 1
		return (2 ** count - 1) % mod


class Solution:

	def numberOfSubsequences(ob, N, A):
		count1 = 0
		for i in A:
			if i & i - 1 == 0:
				count1 += 1
		return (2 ** count1 - 1) % (10 ** 9 + 7)


import math

class Solution:

	def numberOfSubsequences(ob, N, A):
		a = []
		for i in A:
			if math.ceil(math.log(i, 2)) == math.log(i, 2):
				a.append(i)
		if len(a) == 0:
			return 0
		else:
			x = 2 ** len(a)
			return (x - 1) % (10 ** 9 + 7)


import math

class Solution:

	def numberOfSubsequences(ob, N, A):
		mod = 10 ** 9 + 7
		arr = []
		for i in range(N):
			if math.ceil(math.log(A[i], 2)) == math.log(A[i], 2):
				arr.append(A[i])
		ans = len(arr)
		if ans == 0:
			return 0
		else:
			x = 2 ** ans
			return (x - 1) % mod


import math

class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		for i in A:
			t = math.log(i, 2)
			if int(t) == t:
				c = c + 1
		return (2 ** c - 1) % (10 ** 9 + 7)


class Solution:

	def isPowerOfTwo(self, num):
		if num == 0:
			return False
		return num & num - 1 == 0

	def numberOfSubsequences(ob, N, A):
		counter = 0
		for element in A:
			if ob.isPowerOfTwo(element):
				counter += 1
		return (pow(2, counter) - 1) % 1000000007


class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		for i in range(N):
			if A[i] & A[i] - 1 == 0:
				c += 1
		mod = 1000000000.0 + 7
		ans = 1
		for i in range(c):
			ans = ans * 2 % mod
		return int(ans - 1)


class Solution:

	def numberOfSubsequences(ob, N, A):
		M = 10 ** 9 + 7
		c = 0

		def powerof2(n):
			if n == 1:
				return True
			elif n % 2 != 0 or n == 0:
				return False
			return powerof2(n / 2)
		for i in range(0, N):
			if powerof2(A[i]):
				c += 1
		return (2 ** c - 1) % M


class Solution:

	def numberOfSubsequences(ob, N, A):
		temp = {}
		for i in A:
			if i == 1:
				temp[1] = temp.get(1, 0) + 1
			elif i & i - 1 == 0:
				temp[2] = temp.get(2, 0) + 1
		temp[1] = temp.get(1, 0)
		temp[2] = temp.get(2, 0)
		return int(pow(2, temp[1]) * pow(2, temp[2]) - 1) % 1000000007


class Solution:

	def numberOfSubsequences(ob, N, A):
		d = [True for i in A if not i & i - 1]
		return (2 ** sum(d) - 1) % (10 ** 9 + 7)


import math

class Solution:

	def numberOfSubsequences(ob, N, A):
		t = 0
		for i in A:
			z = math.log2(i)
			if int(z) == z:
				t += 1
		sol = (2 ** t - 1) % int(10 ** 9 + 7)
		return sol


import math

class Solution:

	def numberOfSubsequences(ob, N, A):
		counti = 0
		for i in A:
			if math.log(i, 2) % 1 == 0:
				counti += 1
		return (2 ** counti - 1) % (10 ** 9 + 7)


import math

class Solution:

	def ispowerof(ob, n):
		if math.ceil(math.log(n, 2)) == math.floor(math.log(n, 2)):
			return True
		return False

	def numberOfSubsequences(ob, N, A):
		k = 0
		for i in A:
			if ob.ispowerof(i):
				k += 1
		return (2 ** k - 1) % 1000000007


from collections import Counter

class Solution:

	def numberOfSubsequences(ob, N, A):
		dic = dict(Counter(A))
		c = 0
		mod = 10 ** 9 + 7
		for i in range(0, 27):
			if 2 ** i in dic:
				c += dic[2 ** i]
		return (2 ** c - 1) % mod


class Solution:

	def power_two(ob, a):
		return (int(a / 2), a % 2)

	def numberOfSubsequences(ob, N, A):
		Mod = 1000000000.0 + 7
		l = 0
		tot = 1
		for i in range(N):
			p = A[i]
			mod = 0
			while p != 1 and p % 2 == 0:
				(p, mod) = ob.power_two(p)
			if p == 1 and mod == 0:
				l += 1
		while l:
			tot = tot * 2 % Mod
			l = l - 1
		return int((tot - 1) % Mod)


import math
m = 10 ** 9 + 7

class Solution:

	def numberOfSubsequences(ob, N, A):
		count = 0
		sum = 0
		ans = 1
		f = math.factorial
		for x in A:
			if x and (not x & x - 1) == True:
				count += 1
		for i in range(1, count + 1):
			ans = ans % m * 2 % m
		return ans - 1


from math import log2

class Solution:

	def numberOfSubsequences(ob, N, A):
		ans = 0
		for i in A:
			s = int(log2(i))
			if 2 ** s == i:
				ans += 1
		return (2 ** ans - 1) % (10 ** 9 + 7)


from itertools import combinations
import math
import functools
import operator

class Solution:

	def numberOfSubsequences(ob, N, A):
		mod = 10 ** 9 + 7
		factor_2 = sum([1 for x in A if x and (not x & x - 1)])
		result = 2 ** factor_2
		return (result % mod - 1) % mod


from math import log

def func(itr):
	itr = log(itr, 2)
	if float(int(itr)) == itr:
		return 1
	else:
		return 0

class Solution:

	def numberOfSubsequences(ob, N, A):
		modulo = 10 ** 9 + 7
		flst = list(map(func, A))
		count = sum(flst)
		return (2 ** count - 1) % modulo


from math import log2

class Solution:

	def numberOfSubsequences(ob, N, A):
		sum = 0
		for i in A:
			k = log2(i)
			if k == int(k):
				sum += 1
		a = 1
		while sum:
			a *= 2
			sum -= 1
		return a % 1000000007 - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		c = 0
		mod = 10 ** 9 + 7
		for i in A:
			if i & i - 1 == 0:
				c += 1
		ans = 1
		while c > 0:
			ans = ans * 2 % mod
			c -= 1
		return ans - 1
		return (2 ** c - 1) % mod


class Solution:

	def getPow(ob, n):
		if n == 0:
			return 1
		mod = 1000000007
		x = ob.getPow(n // 2) % mod
		if n % 2 == 0:
			return x * x % mod
		return 2 * x * x % mod

	def numberOfSubsequences(ob, N, A):
		c = 0
		for v in A:
			if v == 1 or (v != 0 and v & v - 1 == 0):
				c += 1
		return ob.getPow(c) - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		MOD = 10 ** 9 + 7
		factor = sum([1 for x in A if x and (not x & x - 1)])
		result = 2 ** factor
		return (result % MOD - 1) % MOD


class Solution:

	def is_power(self, x):
		return x and (not x & x - 1)

	def numberOfSubsequences(self, N, A):
		res = 0
		for n in A:
			res += 1 if self.is_power(n) else 0
		ans = 2 ** res
		return ans % (10 ** 9 + 7) - 1


class Solution:

	def numberOfSubsequences(ob, N, A):
		f = 2 ** 30
		j = 0
		for i in A:
			if f % i == 0:
				j = j + 1
		return (2 ** j - 1) % 1000000007