Given an integer, check whether it is Bleak or not. 
A number n is called Bleak if it can be represented as sum of a positive number x and set bit count in x, i.e., x + countSetBits(x) is not equal to n for any non-negative number x.
Example 1:
Input: 4
Output: 1
Explanation: There is no any possible x
such that x + countSetbit(x) = 4
Example 2:
Input: 3
Output: 0
Explanation: 3 is a Bleak number as 
2 + countSetBit(2) = 3.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function is_bleak() which takes n as input parameter and returns 1 if n is not a Bleak number otherwise returns 0.
 
Expected Time Complexity: O(log(n) * log(n))
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

	def is_bleak(self, n):

		# Code here

Solutions:
def count_set_bits(n):
	ret = 0
	while n:
		if n & 1:
			ret += 1
		n >>= 1
	return ret

class Solution:

	def is_bleak(self, n):
		a = 0
		for j in range(14, -1, -1):
			if n > j:
				a = j
				break
		for m in range(n - a, n):
			if count_set_bits(m) + m == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		for x in range(n):
			cb = bin(x).count('1')
			if x + cb == n:
				return 0
		return 1


class Solution:
	d = {}
	for i in range(10 ** 4):
		temp = i
		count = 0
		ans = 0
		while temp:
			temp = temp & temp - 1
			count += 1
		ans = i + count
		d[ans] = i

	def is_bleak(self, n):
		if n in self.d:
			return 0
		return 1


class Solution:

	def is_bleak(self, n):
		from math import log2, ceil
		for i in range(1, ceil(log2(10 ** 4)) + 1):
			(v, cnt) = (n - i, 0)
			while v > 0:
				v &= v - 1
				cnt += 1
			if cnt == i:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):

		def f(a):
			cnt = 0
			while a > 0:
				cnt += 1
				a = a & a - 1
			return cnt
		for i in range(n - 32, n):
			if f(i) + i == n:
				return 0
		return 1


import re

class Solution:

	def is_bleak(self, n):
		for i in range(n):
			bi = str(bin(i))
			no_of_1 = bi.count('1')
			if no_of_1 + i == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		m = len(bin(n)[2:])
		for i in range(1, m + 1):
			if sum((item == '1' for item in bin(n - i)[2:])) == i:
				return 0
		return 1


class Solution:

	def countSetBits(self, x):
		count = 0
		while x:
			x = x & x - 1
			count = count + 1
		return count

	def ceilLog2(self, x):
		count = 0
		x = x - 1
		while x > 0:
			x = x >> 1
			count = count + 1
		return count

	def is_bleak(self, n):
		for x in range(n - self.ceilLog2(n), n):
			if x + self.countSetBits(x) == n:
				return 0
		return 1


from math import log, ceil

def countset(x):
	count = 0
	while x:
		x = x & x - 1
		count = count + 1
	return count

class Solution:

	def is_bleak(self, n):
		cei = ceil(log(n, 2))
		for i in range(n - cei, n):
			if i + countset(i) == n:
				return 0
		return 1


from math import log

class Solution:

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

	def is_bleak(self, n):
		cn = n - len(bin(n)[2:])
		for x in range(cn, n + 1):
			if x + self.count(x) == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		for i in range(1, n):
			x = bin(i)[2:].count('1')
			if i + x == n:
				return 0
		return 1


import math

class Solution:

	def is_bleak(self, n):
		count = 0
		tmp = n
		while n > 0:
			n >>= 1
			count += 1
		i = tmp - count
		while i < tmp:
			if i + self.countbits(i) == tmp:
				return 0
			i += 1
		return 1

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


class Solution:

	def is_bleak(self, n):
		for i in range(n - 32, n, 1):
			if i > 0 and n - i > 0 and (bin(i).count('1') == n - i):
				return 0
		return 1


def setb(n):
	return bin(n).count('1')

class Solution:

	def is_bleak(self, n):
		for i in range(1, n):
			if i + setb(i) == n:
				return 0
		return 1


def countSetBits(num):
	count = 0
	while num > 0:
		mask = num - 1
		num &= mask
		count += 1
	return count

class Solution:

	def is_bleak(self, n):
		for ele in range(n):
			if ele + countSetBits(ele) == n:
				return 0
		else:
			return 1


class Solution:

	def total_bits(self, m):
		res = 0
		while m:
			res += 1
			m //= 2
		return res

	def set_bits(self, m):
		res = 0
		while m:
			res += m % 2
			m //= 2
		return res

	def is_bleak(self, n):
		for num in range(max(n - self.total_bits(n), 1), n):
			if num + self.set_bits(num) == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		dp = [0] * (n + 1)
		for i in range(1, n):
			if i % 2:
				dp[i] = dp[i - 1] + 1
			else:
				dp[i] = dp[i // 2]
			if i + dp[i] == n:
				return 0
		return 1


from collections import Counter

class Solution:

	def is_bleak(self, n):
		for i in range(n):
			if bin(i).count('1') + i == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		for d in range(n // 2, n):
			count = 0
			x = d
			while d > 0:
				if d & (d & -d) > 0:
					count += 1
				d = d - (d & -d)
			if x + count == n:
				return 0
		return 1


class Solution:

	def countBits(self, n):
		c = 0
		while n:
			n &= n - 1
			c += 1
		return c

	def is_bleak(self, n):
		for i in range(n - 1, 0, -1):
			if i + self.countBits(i) == n:
				return 0
		return 1


class Solution:
	num_bits = 32

	def count_set_bits(self, x):
		set_bits = 0
		while x:
			set_bits += 1
			x = x & x - 1
		return set_bits

	def is_bleak(self, n):
		x = max(1, n - self.num_bits)
		while x < n:
			if x + self.count_set_bits(x) == n:
				return 0
			x += 1
		return 1


class Solution:

	def count_set(self, x):
		count = 0
		while x:
			count += x & 1
			x >>= 1
		return count

	def is_bleak(self, n):
		for i in range(n, 0, -1):
			if i + self.count_set(i) == n:
				return 0
		return 1


def countSetBits(x):
	count = 0
	while x:
		x = x & x - 1
		count = count + 1
	return count

def ceilLog2(x):
	count = 0
	x = x - 1
	while x > 0:
		x = x >> 1
		count = count + 1
	return count

class Solution:

	def is_bleak(self, n):
		for x in range(n - ceilLog2(n), n):
			if x + countSetBits(x) == n:
				return 0
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


class Solution:

	def is_bleak(self, n):
		z = n
		c = 0
		while z > 0:
			z = z // 2
			c = c + 1
		mina = n - c
		for i in range(n - c, n):
			z = i
			sb = 0
			while z > 0:
				a = z % 2
				z = z // 2
				if a == 1:
					sb = sb + 1
			if sb + i == n:
				return 0
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


class Solution:

	def is_bleak(self, n):
		l = n // 2
		r = n
		ans = 1
		while r:
			mid_bits = setBits(r)
			if n == r + mid_bits:
				ans = 0
				break
			r -= 1
		return ans

def setBits(n):
	count = 0
	while n:
		n = n & n - 1
		count += 1
	return count
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


class Solution:

	def is_bleak(self, n):

		def countSetBits(i):
			a = '{0:b}'.format(i)
			return a.count('1')
		for i in range(0, n):
			if i + countSetBits(i) == n:
				return 0
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


class Solution:

	def is_bleak(self, n):
		for i in range(n):
			cb = bin(i).count('1')
			if i + cb == n:
				return 0
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


import math

class Solution:

	def is_bleak(self, n):
		u = int(math.log(n, 2))
		for i in range(n - u, n):
			if i + count(i) == n:
				return 0
		return 1

def count(i):
	count1 = 0
	while i > 0:
		if i & 1 == 1:
			count1 += 1
		i >>= 1
	return count1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


class Solution:

	def is_bleak(self, n):
		res = 0
		num = 1
		while num < n:
			res = 0
			binary = str(bin(num)[2:])
			ones = binary.count('1')
			res = num + ones
			if res == n:
				return 0
			num += 1
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


class Solution:

	def set_bits(self, n):
		cnt = 0
		while n:
			if n & 1:
				cnt += 1
			n = n >> 1
		return cnt

	def log2(self, n):
		cnt = 0
		n = n - 1
		while n:
			n = n >> 1
			cnt += 1
		return cnt

	def is_bleak(self, n):
		x = n - self.log2(n)
		for i in range(x, n + 1):
			if i + self.set_bits(i) == n:
				return 0
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


import math

def countSetBits(n):
	k = 0
	while n:
		n = n ^ n & -n
		k += 1
	return k

class Solution:

	def is_bleak(self, n):
		for i in range(n - math.ceil(math.log(n, 2)), n):
			if i + countSetBits(i) == n:
				return 0
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_bleak(n)
		print(ans)


class Solution:

	def is_bleak(self, n):
		for _ in range(n):
			flag = 0
			if n > 14:
				s = n - 14
			else:
				s = 1
			for i in range(s, n):
				if i + bin(i)[2:].count('1') == n:
					flag = 1
					break
			if flag:
				return 0
			else:
				return 1


class Solution:

	def is_bleak(self, n):
		c = 1
		for i in range(n):
			if i + bin(i).count('1') == n:
				c = 0
				break
		return c


class Solution:

	def setBits(self, N):
		cnt = 0
		while N != 0:
			N = N & N - 1
			cnt += 1
		return cnt

	def is_bleak(self, n):
		for i in range(1, n):
			b = self.setBits(i) + i
			if b == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		dp = [0] * (10 ** 4 + 1)
		dp[1] = 1
		dp[2] = 1
		dp[3] = 2
		for i in range(n):
			dp[i] = dp[i // 2]
			if i % 2:
				dp[i] += 1
		for i in range(n):
			if i + dp[i] == n:
				return 0
		return 1


import math

class Solution:

	def countSetBits(self, x):
		bi = bin(x)[2:]
		bi = [int(x) for x in str(bi)]
		ones = bi.count(1)
		return ones

	def ceilLog2(self, x):
		count = 0
		x -= 1
		while x > 0:
			x = x >> 1
			count += 1
		return count

	def is_bleak(self, n):
		for x in range(n - self.ceilLog2(n), n):
			if x + self.countSetBits(x) == n:
				return 0
		return 1


class Solution:

	def countSetBits(self, x):
		k = bin(x).replace('b', '')
		return k.count('1')

	def is_bleak(self, n):
		for x in range(n):
			if self.countSetBits(x) + x == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		z = n
		c = 0
		while z > 0:
			z = z // 2
			c = c + 1
		mina = n - c
		for i in range(n - c, n):
			z = i
			sb = 0
			while z > 0:
				a = z % 2
				z = z // 2
				if a == 1:
					sb = sb + 1
			if sb + i == n:
				return 0
		return 1


def csb(n):
	b = bin(n).replace('b', '')
	return b.count('1')

class Solution:

	def is_bleak(self, n):
		if n == 1:
			return 1
		for i in range(n):
			if i + csb(i) == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		for i in range(n - 1, 0, -1):
			if i + self.count(i) == n:
				return 0
		return 1

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


class Solution:

	def is_bleak(self, n):
		for i in range(n - 1, 0, -1):
			c = 0
			t = i
			while t > 0:
				t = t & t - 1
				c += 1
			x1 = c
			if n == x1 + i:
				return 0
		return 1


class Solution:

	def setbit(self, i):
		c = 0
		while i:
			i = i & i - 1
			c += 1
		return c

	def is_bleak(self, n):
		for j in range(n - 1, 0, -1):
			a = self.setbit(j)
			if n - a == j:
				return 0
		return 1


class Solution:
	table = [-1 for i in range(10 ** 4 + 1)]

	def countSetBits(self, n):
		if self.table[n] != -1:
			return self.table[n]
		set_bits = 0
		while n:
			if n & 1:
				set_bits += 1
			n = n >> 1
		self.table[n] = set_bits
		return set_bits

	def is_bleak(self, n):
		for i in range(n - 1, 0, -1):
			set_bits = 0
			if self.table[i] != -1:
				set_bits = self.table[i]
			else:
				y = i
				while y:
					if y & 1:
						set_bits += 1
					y = y >> 1
				self.table[y] = set_bits
			if i + set_bits == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		a = 1
		i = 1
		while a < n:
			a *= 2
			i += 1
		for x in range(n - i, n):
			if x + self.countSetBits(x) == n:
				return 0
		return 1

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


class Solution:

	def is_bleak(self, n):
		low = 0
		high = n
		for i in range(n, 0, -1):
			count = 0
			mask = 1
			num = i
			while num:
				if num & mask == 1:
					count += 1
				num >>= 1
			if i + count == n:
				return 0
		else:
			return 1


class Solution:

	def is_bleak(self, n):

		def findBits(x):
			cnt = 0
			while x:
				x = x & x - 1
				cnt += 1
			return cnt
		for i in range(1, n + 1):
			if i + findBits(i) == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		(l, r) = (1, n)
		for i in range(1, n + 1):
			if i + self.countSetBits(i) == n:
				return 0
		return 1

	def countSetBits(self, num):
		cnt = 0
		while num != 0:
			num = num & num - 1
			cnt += 1
		return cnt


class Solution:

	def is_bleak(self, n):

		def countSetbit(n):
			count = 0
			while n:
				count += n & 1
				n >>= 1
			return count
		a = n - 17
		m = 1
		for i in range(a, n):
			if i > 0 and i + countSetbit(i) == n:
				m = 0
				break
		return m


import math

def countSetBits(x):
	r = str(format(x, 'b')).count('1')
	return r

class Solution:

	def is_bleak(self, n):
		for i in range(1, n):
			if i + countSetBits(i) == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):
		if n == 1:
			return 1
		else:
			for i in range(n - 1, 0, -1):
				t = i
				count = 0
				while t > 0:
					t = t & t - 1
					count = count + 1
				if count + i == n:
					return 0
			return 1


import math

class Solution:

	def set_bits(abc, num):
		count = 0
		while num > 0:
			if num % 2 == 1:
				count += 1
			num >>= 1
		return count

	def is_bleak(self, n):
		check = math.ceil(math.log(n, 2))
		for i in range(n - check, n):
			if i + Solution().set_bits(i) == n:
				return 0
		return 1


class Solution:

	def check(self, x):
		cnt = 0
		while x:
			x = x & x - 1
			cnt += 1
		return cnt

	def is_bleak(self, n):
		if n == 1:
			return 1
		ans = 1
		for i in range(1, n):
			if i + self.check(i) == n:
				ans = 0
				break
		return ans


class Solution:

	def is_bleak(self, n):
		flag = 1
		for i in range(n, 0, -1):
			b = self.setbit(i) + i
			if b == n:
				flag = 0
				break
		return flag

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


class Solution:

	def is_bleak(self, n):
		for i in range(1, n + 1):
			x = i
			z = bin(i).replace('0b', '')
			x1 = z.count('1')
			if int(x1) + x == n:
				return 0
		else:
			return 1


class Solution:

	def set_bits(self, n):
		bin_num = bin(n).replace('Ob', '')
		set_bits = str(bin_num).count('1')
		return set_bits

	def is_bleak(self, n):
		for i in range(n):
			if i + self.set_bits(i) == n:
				return 0
		return 1


class Solution:

	def sol(self, num):
		ans = 0
		while num:
			num = num & num - 1
			ans = ans + 1
		return ans

	def is_bleak(self, n):
		for i in range(1, n):
			if i + self.sol(i) == n:
				return 0
		return 1


class Solution:

	def is_bleak(self, n):

		def countSetbit(mid):
			count = 0
			while mid:
				mid = mid & mid - 1
				count += 1
			return count
		for i in range(1, n):
			count = countSetbit(i)
			if count + i == n:
				return 0
		return 1