Shreyansh has an integer N. He is really curious about the binary representation of integers. He sees that any given integer has a number of set bits. Now he wants to find out that how many positive integers, strictly less than N, have the same number of set bits as N.
He is a little weak in maths. Help him find the number of integers.
Note : Since N takes large values, brute force won't work.
 
Example 1:
Input:
N = 8
Output: 3
Explanation:
Binary representation of 8 : 1000
So the integers less than 8 with 
same number of set bits are : 4, 2, 1
Hence, the result is 3.  
 
Example 2:
Input:
N = 4
Output: 2
Explanation:
Binary representation of 4 : 100
So the integers less than 4 with 
same number of set bits are : 2, 1
So, The result is 2.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function count() which takes the integer N as input parameters and returns the required answer.
Expected Time Complexity: O(log(n))
Expected Auxiliary Space: O(log(n)*log(n))
 
 
Constraints : 
1 <= N <= 10^12

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: class Solution:

    def count (self, N):

        # code here 



Solutions:
from math import factorial

class Solution:

	def ncr(self, n, r):
		if n >= r:
			return int(factorial(n) / (factorial(r) * factorial(n - r)))
		return 0

	def count(self, N):
		bina = list(map(int, bin(N)[2:]))
		res = 0
		for i in range(len(bina)):
			if bina[i] == 1:
				r = sum(bina[i:])
				n = len(bina) - 1 - i
				res = res + ob.ncr(n, r)
		return res


import math

class Solution:

	def count(self, N):
		box = '%s' % bin(N)
		num = box.count('1')
		ans = 0
		for i in range(2, len(box) - 1):
			q = len(box[i + 1:len(box)])
			if num > q:
				continue
			if box[i] == '1':
				ans += int(math.factorial(q) / (math.factorial(num) * math.factorial(q - num)))
				num -= 1
		return ans


class Solution:

	def ncr(self, n, r):
		if r > n:
			return 0
		if r == 0 or r == n:
			return 1
		if self.cache[n][r] != -1:
			return self.cache[n][r]
		res = self.ncr(n - 1, r - 1) + self.ncr(n - 1, r)
		self.cache[n][r] = res
		return res

	def count(self, N):
		self.cache = [[-1] * 40 for _ in range(40)]
		res = 0
		ones = 0
		bits = 0
		while N != 0:
			if N & 1:
				res += self.ncr(bits, ones + 1)
				ones += 1
			bits += 1
			N >>= 1
		return res


class Solution:

	def count(self, N):

		def nck(n, r):
			if r > n:
				return 0
			res = 1
			for i in range(r):
				res *= n - i
				res //= i + 1
			return res
		if N == 1:
			return 0
		num = N
		cnt = 0
		i = 0
		ans = 0
		while num != 0:
			if num & 1 == 1:
				cnt += 1
				ans += nck(i, cnt)
			i += 1
			num >>= 1
		return ans


import math

class Solution:

	def count(self, N):
		count = 0
		(ones, z) = (0, 0)
		while N:
			if N & 1:
				ones += 1
				if ones <= z:
					count += math.factorial(z) // (math.factorial(ones) * math.factorial(z - ones))
			z += 1
			N = N >> 1
		return count


from math import log2, floor, factorial
from functools import reduce

class Solution:

	def count(self, N):

		def cnk(n, k):
			if k > n:
				return 0
			return reduce(lambda acc, e: acc * e, range(n - k + 1, n + 1), 1) // int(factorial(k))
		(ans, bits) = (0, 0)
		n = floor(log2(N)) + 1
		for i in range(n + 1):
			if N & 1 << i != 0:
				bits += 1
				ans += cnk(i, bits)
		return ans


import math

class Solution:

	def count(self, n):
		ans = 0

		def isKthSet(n, k):
			if n & 1 << k:
				return True
			else:
				return False

		def comb(n, r):
			ans = math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
			return ans
		no_one = 0
		i = 0
		total_bits = math.floor(math.log(n, 2))
		while i <= total_bits:
			if isKthSet(n, i):
				if i != 0:
					if no_one < i:
						ans += comb(i, no_one + 1)
				no_one += 1
			i += 1
		return ans


class Solution:

	def comb(self, n, r):
		return self.fact(n) // (self.fact(n - r) * self.fact(r))

	def fact(self, n):
		if n == 0:
			return 1
		else:
			return self.fact(n - 1) * n

	def solve(self, x, one, start, n):
		if start == n:
			return 0
		elif x[start] == '0':
			start += 1
			return self.solve(x, one, start, n)
		elif x[start] == '1' and n - start - 1 >= one:
			return self.comb(n - start - 1, one) + self.solve(x, one - 1, start + 1, n)
		else:
			return 0

	def reverse1(self, s):
		out = ''
		n = len(s) - 1
		for i in range(n, -1, -1):
			out += s[i]
		return out

	def count(self, x):
		s = ''
		one = 0
		while x >= 0:
			y = x % 2
			if y == 1:
				one += 1
			s = s + str(y)
			if x == 1 or x == 0:
				break
			x //= 2
		s = self.reverse1(s)
		n = len(s)
		out = self.solve(s, one, 0, n)
		return out


class Solution:

	def fact(self, n):
		res = 1
		for i in range(2, n + 1):
			res *= i
		return res

	def combi(self, n, r):
		if n == 0 or n < r:
			return 0
		return self.fact(n) / self.fact(r) / self.fact(n - r)

	def count(self, N):
		st = bin(N)[2:]
		res = 0
		count1 = 0
		l = len(st)
		for i in range(l - 1, -1, -1):
			if st[i] == '1':
				count1 += 1
				res += self.combi(l - i - 1, count1)
		return round(res)


from math import factorial

class Solution:

	def count(self, N):

		def ncr(n, r):
			if r > n:
				return 0
			return factorial(n) // (factorial(r) * factorial(n - r))
		n = bin(N)[2:]
		(bit, sett) = (0, 0)
		res = 0
		for i in range(len(n) - 1, -1, -1):
			if n[i] == '0':
				bit += 1
			else:
				bit += 1
				sett += 1
				res += ncr(bit - 1, sett)
		return res


class Solution:

	def count(self, N):

		def fac(n):
			if n == 1:
				return 1
			t = n * fac(n - 1)
			factorial[n] = t
			return factorial[n]
		bin_n = bin(N).split('0b')[1]
		n = len(bin_n)
		factorial = [1] * (n + 1)
		n = len(bin_n)
		fac(n)
		ans = 0
		once = bin_n.count('1')
		for i in range(n - 1):
			if bin_n[i] == '1':
				nn = n - (i + 1)
				ans += factorial[nn] / (factorial[once] * factorial[nn - once])
				once -= 1
			if once <= 0:
				break
		return int(ans)


class Solution:

	def fact(self, n):
		if n == 0 or n == 1:
			return 1
		d = 1
		for i in range(1, n + 1):
			d *= i
		return d

	def ncr(self, n, r):
		if r > n:
			return 0
		ff = self.fact(n) // (self.fact(r) * self.fact(n - r))
		return ff

	def count(self, N):
		i = 1
		ans = 0
		one = 0
		while N > 0:
			if N & 1 == 1:
				one += 1
				k = self.ncr(i - 1, one)
				ans += k
			i += 1
			N = N >> 1
		return ans


def ncr(n, r, dp):
	if r > n:
		return 0
	if r == 0 or r == n:
		return 1
	if dp[n][r] != -1:
		return dp[n][r]
	ans = ncr(n - 1, r - 1, dp) + ncr(n - 1, r, dp)
	dp[n][r] = ans
	return ans

class Solution:

	def count(self, N):
		dp = [[-1 for i in range(100)] for i in range(100)]
		bits = 0
		ans = 0
		setbits = 0
		while N:
			if N & 1:
				setbits += 1
				ans += ncr(bits, setbits, dp)
			bits += 1
			N >>= 1
		return ans


class Solution:

	def factorial(self, n):
		if n == 0:
			return 1
		return n * self.factorial(n - 1)

	def fact(self, n, r):
		n1 = self.factorial(n)
		r1 = self.factorial(r)
		n_r = self.factorial(abs(n - r))
		return n1 // (n_r * r1)

	def count(self, N):
		ans = 0
		ori = bin(N)[2:]
		for i in range(len(ori)):
			if ori[i] == '1' and i != len(ori) - 1:
				set_bits = 1
				rest = 0
				for j in range(i + 1, len(ori)):
					if ori[j] == '1':
						set_bits += 1
					rest += 1
				ans += self.fact(rest, set_bits)
		return ans


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def count(self, N):

		def fact(num):
			if num == 1 or num == 0:
				return 1
			return num * fact(num - 1)
		ans = 0
		binary = str(bin(N))[2:]
		n = len(binary)
		count_one = 0
		for i in binary:
			if i == '1':
				count_one += 1
		for i in range(n - 1):
			if binary[i] == '1':
				empty_post = n - (i + 1)
				if empty_post < count_one:
					break
				upper = fact(empty_post)
				lower = fact(count_one) * fact(empty_post - count_one)
				ans += upper / lower
				count_one -= 1
		return int(ans)


class Solution:

	def count(self, N):
		dp = [[-1] * 50 for _ in range(50)]

		def solve(spots, ones):
			if ones > spots:
				return 0
			if ones == 0 or ones == spots:
				return 1
			if dp[spots][ones] != -1:
				return dp[spots][ones]
			res = solve(spots - 1, ones - 1) + solve(spots - 1, ones)
			dp[spots][ones] = res
			return res
		out = 0
		ones = 0
		bits = 0
		while N != 0:
			if N & 1:
				out += solve(bits, ones + 1)
				ones += 1
			bits += 1
			N >>= 1
		return out


class Solution:

	def count(self, N):
		from math import factorial
		dp = [[-1] * 50 for i in range(50)]

		def ncr(n, r):
			if n < r:
				return 0
			if dp[n][r] != -1:
				return dp[n][r]
			dp[n][r] = factorial(n) // (factorial(n - r) * factorial(r))
			return dp[n][r]
		pos = 0
		ones = 0
		ans = 0
		while N:
			if N & 1:
				ones += 1
				ans += ncr(pos, ones)
			pos += 1
			N >>= 1
		return ans


class Solution:

	def count(self, N):
		dp = [[-1] * 50 for i in range(50)]

		def ncr(n, r):
			if r > n:
				return 0
			if n == r or r == 0:
				return 1
			if dp[n][r] != -1:
				return dp[n][r]
			dp[n][r] = ncr(n - 1, r - 1) + ncr(n - 1, r)
			return dp[n][r]
		pos = 0
		ones = 0
		ans = 0
		while N:
			if N & 1:
				ones += 1
				ans += ncr(pos, ones)
			pos += 1
			N >>= 1
		return ans


class Solution:

	def count(self, n):

		def nck(n, r):
			if r > n:
				return 0
			res = 1
			for i in range(r):
				res *= n - i
				res //= i + 1
			return res
		if N == 1:
			return 0
		num = N
		cnt = 0
		i = 0
		ans = 0
		while num != 0:
			if num & 1 == 1:
				cnt += 1
				ans += nck(i, cnt)
			i += 1
			num >>= 1
		return ans
		des = []
		limit = int(format(n, '0b'))

		def permutation(l, c, m):
			if l == 0 and c == 0:
				if m < limit:
					des.append(m)
			else:
				if l > 0 and m * 10 + 0 < limit:
					permutation(l - 1, c, m * 10 + 0)
				if c > 0 and m * 10 + 1 < limit:
					permutation(l, c - 1, m * 10 + 1)
		count = 0
		lens = 0
		k = n
		while n:
			count += n & 1
			n >>= 1
			lens += 1
		permutation(lens - count, count, 0)
		return len(des)


class Solution:

	def f(self, n, m):
		if n == 0:
			return 0
		if n < m:
			return 0
		x = 1
		r2 = 1
		if n - m > m:
			for i in range(n, n - m, -1):
				x = x * i
			for j in range(1, m + 1):
				r2 = r2 * j
			return x / r2
		else:
			for i in range(n, m, -1):
				x = x * i
			for j in range(1, n - m + 1):
				r2 = r2 * j
			return x / r2

	def count(self, N):
		n = bin(N).replace('0b', '')
		n0 = 0
		n1 = 0
		c = 0
		for i in range(len(n) - 1, -1, -1):
			if n[i] == '1':
				n1 = n1 + 1
				c = c + self.f(len(n) - i - 1, n1)
		return int(c)


class Solution:

	def count(self, N):

		def c(n, r):
			if r > n:
				return 0
			res = 1
			for i in range(r):
				res *= n - i
				res /= i + 1
			return res
		i = 0
		ans = 0
		cnt = 0
		while N:
			if N & 1 == 1:
				cnt += 1
				ans += c(i, cnt)
			i += 1
			N >>= 1
		return int(ans)


import math

class Solution:

	def count(self, N):
		permutations = 0
		count_0 = 0
		count_1 = 0
		bits = format(N, 'b')
		for bit in bits[::-1]:
			if bit == '0':
				count_0 += 1
				continue
			count_1 += 1
			if count_0 == 0:
				continue
			bits_count_without_most_significant = count_1 + count_0 - 1
			count_0_without_most_significant = bits_count_without_most_significant - count_1
			permutations += math.factorial(bits_count_without_most_significant) / (math.factorial(count_1) * math.factorial(count_0_without_most_significant))
		return int(permutations)


class Solution:

	def comb(self, n, r):
		if r > n:
			return 0
		if n == 0:
			return 0
		if r == 0:
			return 1
		if r == 1:
			return n
		if r > n - r:
			r = n - r
		ans = 1
		for i in range(1, r + 1):
			ans *= n - r + i
			ans //= i
		return ans

	def count(self, N):
		bitPosition = 1
		setBitsCount = 0
		ans = 0
		while N:
			if N & 1:
				setBitsCount += 1
				ans += self.comb(bitPosition - 1, setBitsCount)
			N >>= 1
			bitPosition += 1
		return ans


class Solution:

	def count(self, Num):

		def ncr(n, r):
			if r > n:
				return 0
			N = 1
			D = 1
			while r > 0:
				N *= n
				D *= r
				n -= 1
				r -= 1
			return N / D
		if Num == 1:
			return 0
		i = 0
		ans = 0
		cnt = 0
		while Num != 0:
			if Num & 1 == 1:
				cnt += 1
				ans += ncr(i, cnt)
			Num >>= 1
			i += 1
		return int(ans)


class Solution:

	def count(self, N):
		dp = [[-1] * 64 for i in range(64)]

		def solve(spots, ones):
			if ones > spots:
				return 0
			if ones == 0 or ones == spots:
				return 1
			if dp[spots][ones] != -1:
				return dp[spots][ones]
			res = solve(spots - 1, ones - 1) + solve(spots - 1, ones)
			dp[spots][ones] = res
			return res
		out = 0
		ones = 0
		for i in range(64):
			if N & 1:
				ones += 1
				out += solve(i, ones)
			N >>= 1
			if N == 0:
				break
		return out


def bit_count(N):
	t = 0
	while N > 0:
		d = N % 2
		N = int(N / 2)
		if d == 1:
			t += 1
	return t

class Solution:

	def ncr(self, n, r):
		if r > n:
			return 0
		if r == 0 or r == n:
			return 1
		if self.cache[n][r] != -1:
			return self.cache[n][r]
		res = self.ncr(n - 1, r - 1) + self.ncr(n - 1, r)
		self.cache[n][r] = res
		return res

	def count(self, N):
		self.cache = [[-1] * 40 for _ in range(40)]
		res = 0
		ones = 0
		bits = 0
		while N != 0:
			if N & 1:
				res += self.ncr(bits, ones + 1)
				ones += 1
			bits += 1
			N >>= 1
		return res


class Solution:

	def count(self, n):
		dp = [[-1 for i in range(64)] for j in range(64)]

		def nCr(n, r):
			if r > n:
				return 0
			if r == 0 or r == n:
				return 1
			if dp[n][r] != -1:
				return dp[n][r]
			dp[n][r] = nCr(n - 1, r - 1) + nCr(n - 1, r)
			return dp[n][r]
		ones = 0
		positions = 0
		ans = 0
		while n > 0:
			if n & 1 == 1:
				ones += 1
				ans += nCr(positions, ones)
			n = n >> 1
			positions += 1
		return ans


class Solution:
	cache = [[-1] * 40 for _ in range(40)]

	def count(self, N):
		(ones, res) = (0, 0)
		for i in range(40):
			if N & 1 == 1:
				ones += 1
				res += self.C(i, ones)
			N >>= 1
		return res

	def C(self, n, r):
		if n < r:
			return 0
		if n == r or r == 0:
			return 1
		if self.cache[n][r] != -1:
			return self.cache[n][r]
		res = self.C(n - 1, r - 1) + self.C(n - 1, r)
		self.cache[n][r] = res
		return res


class Solution:

	def count(self, N):
		(ones, res) = (0, 0)
		for i in range(40):
			if N & 1 == 1:
				ones += 1
				res += self.C(i, ones)
			N >>= 1
		return res

	def C(self, n, r):
		if n < r:
			return 0
		if n == r or r == 0:
			return 1
		a = max(n - r, r)
		res = n
		for i in range(a + 1, n):
			res *= i
		return res // self.fac(n - r) if a == r else res // self.fac(r)

	def fac(self, n):
		return 1 if n <= 1 else n * self.fac(n - 1)


class Solution:

	def csb(self, n):
		count = 0
		while n > 0:
			n &= n - 1
			count += 1
		return count

	def ncr(self, n, r):
		if n < r:
			return 0
		res = 1
		for i in range(r):
			res *= n - i
			res //= i + 1
		return res

	def rec(self, N, setBits, l):
		if l == 0:
			return 0
		mask = 1 << l
		res = 0
		if mask & N:
			res1 = self.rec(N, setBits - 1, l - 1)
			res0 = self.ncr(l, setBits)
			res = res0 + res1
		else:
			res = self.rec(N, setBits, l - 1)
		return res

	def count(self, N):
		setBits = self.csb(N)
		return self.rec(N, setBits, 63)


class Solution:

	def fact(self, n):
		if n == 0:
			return 1
		return n * self.fact(n - 1)

	def count(self, N):
		r = 0
		i = 0
		ans = 0
		while N != 0:
			if N & 1 == 1:
				r += 1
				if i == 0:
					ans = 0
				else:
					ans += self.fact(i) // (self.fact(r) * self.fact(abs(i - r)))
			i += 1
			N = N >> 1
		return ans


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		p = 1
		for i in range(r):
			p = p * n
			n -= 1
		q = r
		for i in range(q):
			p = p // r
			r -= 1
		return p

	def count(self, N):
		ones = 0
		c = 0
		ans = 0
		while N != 0:
			if N % 2 == 1:
				ones += 1
				ans += self.nCr(c, ones)
			N = N // 2
			c += 1
		return ans


import sys
sys.setrecursionlimit(100000)

class Solution:

	def count(self, N):

		def nCr(n, r):
			if r > n:
				return 0
			ans = 1
			for i in range(r):
				ans *= n - i
				ans /= i + 1
			return int(ans)
		if N == 1:
			return 0
		n = N
		cnt = 0
		i = 0
		ans = 0
		while n:
			if n & 1 == 1:
				cnt += 1
				ans += nCr(i, cnt)
			i += 1
			n >>= 1
		return ans


import operator as op
from functools import reduce

class Solution:

	def ncr(self, n, r):
		r = min(r, n - r)
		numer = reduce(op.mul, range(n, n - r, -1), 1)
		denom = reduce(op.mul, range(1, r + 1), 1)
		return numer // denom

	def findbits(self, n):
		l = []
		ones = 0
		while n > 0:
			rem = n % 2
			l.append(rem)
			n = int(n / 2)
			if rem == 1:
				ones = ones + 1
		return (l, ones)

	def count(self, N):
		val = self.findbits(N)
		l = val[0]
		ones = val[1]
		n = len(l)
		ans = 0
		tone = ones
		for i in range(n - 1, -1, -1):
			if l[i] == 1:
				if i > 0 and tone <= i:
					ans = ans + self.ncr(i, tone)
				tone = tone - 1
		return ans