# Check if a number is Bleak

A number ‘n’ is called Bleak if it cannot 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.

Examples :

```Input : n = 3
Output : false
3 is not Bleak as it can be represented
as 2 + countSetBits(2).

Input : n = 4
Output : true
4 is t Bleak as it cannot be represented
as sum of a number x and countSetBits(x)
for any number x.```

Method 1 (Simple)

```bool isBleak(n)
1) Consider all numbers smaller than n
a) If x + countSetBits(x) == n
return false

2) Return true
```

Below is the implementation of the simple approach.

## C++

 `// A simple C++ program to check Bleak Number ` `#include ` `using` `namespace` `std; ` ` `  `/* Function to get no of set bits in binary ` `   ``representation of passed binary no. */` `int` `countSetBits(``int` `x) ` `{ ` `    ``unsigned ``int` `count = 0; ` `    ``while` `(x) { ` `        ``x &= (x - 1); ` `        ``count++; ` `    ``} ` `    ``return` `count; ` `} ` ` `  `// Returns true if n is Bleak ` `bool` `isBleak(``int` `n) ` `{ ` `    ``// Check for all numbers 'x' smaller ` `    ``// than n.  If x + countSetBits(x) ` `    ``// becomes n, then n can't be Bleak ` `    ``for` `(``int` `x = 1; x < n; x++) ` `        ``if` `(x + countSetBits(x) == n) ` `            ``return` `false``; ` ` `  `    ``return` `true``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``isBleak(3) ? cout << ````"Yes "``` `: cout << ````"No "````; ` `    ``isBleak(4) ? cout << ````"Yes "``` `: cout << ````"No "````; ` `    ``return` `0; ` `} `

## Java

 `// A simple Java program to check Bleak Number ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``/* Function to get no of set bits in binary ` `       ``representation of passed binary no. */` `    ``static` `int` `countSetBits(``int` `x) ` `    ``{ ` `        ``int` `count = ``0``; ` `        ``while` `(x != ``0``) { ` `            ``x &= (x - ``1``); ` `            ``count++; ` `        ``} ` `        ``return` `count; ` `    ``} ` ` `  `    ``// Returns true if n is Bleak ` `    ``static` `boolean` `isBleak(``int` `n) ` `    ``{ ` `        ``// Check for all numbers 'x' smaller ` `        ``// than n.  If x + countSetBits(x) ` `        ``// becomes n, then n can't be Bleak ` `        ``for` `(``int` `x = ``1``; x < n; x++) ` `            ``if` `(x + countSetBits(x) == n) ` `                ``return` `false``; ` ` `  `        ``return` `true``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``if` `(isBleak(``3``)) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` `        ``if` `(isBleak(``4``)) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` `    ``} ` `} ` ` `  `/*This code is contributed by Nikita Tiwari.*/`

/div>

## Python3

 `# A simple Python 3 program  ` `# to check Bleak Number ` ` `  `# Function to get no of set ` `# bits in binary  ` `# representation of passed  ` `# binary no.  ` `def` `countSetBits(x) : ` `     `  `    ``count ``=` `0` `     `  `    ``while` `(x) : ` `        ``x ``=` `x & (x``-``1``) ` `        ``count ``=` `count ``+` `1` `     `  `    ``return` `count ` `     `  `# Returns true if n ` `# is Bleak ` `def` `isBleak(n) : ` ` `  `    ``# Check for all numbers 'x' ` `    ``# smaller than n. If x +  ` `    ``# countSetBits(x) becomes ` `    ``# n, then n can't be Bleak. ` `    ``for` `x ``in` `range``(``1``, n) : ` `         `  `        ``if` `(x ``+` `countSetBits(x) ``=``=` `n) : ` `            ``return` `False` `             `  `    ``return` `True` `     `  `# Driver code ` `if``(isBleak(``3``)) : ` `    ``print``( ``"Yes"``) ` `else` `: ` `    ``print``(``"No"``) ` ` `  `if``(isBleak(``4``)) : ` `    ``print``(``"Yes"``) ` `else` `:  ` `    ``print``( ``"No"``) ` `     `  `# This code is contributed by Nikita Tiwari. `

## C#

 `// A simple C# program to check ` `// Bleak Number ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``/* Function to get no of set ` `    ``bits in binary representation  ` `    ``of passed binary no. */` `    ``static` `int` `countSetBits(``int` `x) ` `    ``{ ` `        ``int` `count = 0; ` `         `  `        ``while` `(x != 0) { ` `            ``x &= (x - 1); ` `            ``count++; ` `        ``} ` `         `  `        ``return` `count; ` `    ``} ` ` `  `    ``// Returns true if n is Bleak ` `    ``static` `bool` `isBleak(``int` `n) ` `    ``{ ` `         `  `        ``// Check for all numbers ` `        ``// 'x' smaller than n. If ` `        ``// x + countSetBits(x) ` `        ``// becomes n, then n can't ` `        ``// be Bleak ` `        ``for` `(``int` `x = 1; x < n; x++) ` `         `  `            ``if` `(x + countSetBits(x) ` `                              ``== n) ` `                ``return` `false``; ` ` `  `        ``return` `true``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``if` `(isBleak(3)) ` `            ``Console.Write(``"Yes"``); ` `        ``else` `            ``Console.WriteLine(``"No"``); ` `             `  `        ``if` `(isBleak(4)) ` `            ``Console.Write(``"Yes"``); ` `        ``else` `            ``Console.Write(``"No"``); ` `    ``} ` `} ` ` `  `// This code is contributed by ` `// Nitin mittal `

## PHP

 ` `

Output :

```No
Yes```

Time complexity of above solution is O(n Log n).

Method 2 (Efficient)
The idea is based on the fact that the largest count of set bits in any number smaller than n cannot exceed ceiling of Log2n. So we need to check only numbers from range n – ceilingLog2(n) to n.

```bool isBleak(n)
1) Consider all numbers n - ceiling(Log2n) to n-1
a) If x + countSetBits(x) == n
return false

2) Return true
```

Below is the implementation of the idea.

## C++

 `// An efficient C++ program to check Bleak Number ` `#include ` `using` `namespace` `std; ` ` `  `/* Function to get no of set bits in binary ` `   ``representation of passed binary no. */` `int` `countSetBits(``int` `x) ` `{ ` `    ``unsigned ``int` `count = 0; ` `    ``while` `(x) { ` `        ``x &= (x - 1); ` `        ``count++; ` `    ``} ` `    ``return` `count; ` `} ` ` `  `// A function to return ceiling of log x ` `// in base 2. For example, it returns 3 ` `// for 8 and 4 for 9. ` `int` `ceilLog2(``int` `x) ` `{ ` `    ``int` `count = 0; ` `    ``x--; ` `    ``while` `(x > 0) { ` `        ``x = x >> 1; ` `        ``count++; ` `    ``} ` `    ``return` `count; ` `} ` ` `  `// Returns true if n is Bleak ` `bool` `isBleak(``int` `n) ` `{ ` `    ``// Check for all numbers 'x' smaller ` `    ``// than n.  If x + countSetBits(x) ` `    ``// becomes n, then n can't be Bleak ` `    ``for` `(``int` `x = n - ceilLog2(n); x < n; x++) ` `        ``if` `(x + countSetBits(x) == n) ` `            ``return` `false``; ` ` `  `    ``return` `true``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``isBleak(3) ? cout << ````"Yes "``` `: cout << ````"No "````; ` `    ``isBleak(4) ? cout << ````"Yes "``` `: cout << ````"No "````; ` `    ``return` `0; ` `} `

## Java

 `// An efficient Java program to ` `// check Bleak Number ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``/* Function to get no of set bits in ` `    ``binary representation of passed binary ` `    ``no. */` `    ``static` `int` `countSetBits(``int` `x) ` `    ``{ ` `        ``int` `count = ``0``; ` `        ``while` `(x != ``0``) { ` `            ``x &= (x - ``1``); ` `            ``count++; ` `        ``} ` `        ``return` `count; ` `    ``} ` ` `  `    ``// A function to return ceiling of log x ` `    ``// in base 2. For example, it returns 3 ` `    ``// for 8 and 4 for 9. ` `    ``static` `int` `ceilLog2(``int` `x) ` `    ``{ ` `        ``int` `count = ``0``; ` `        ``x--; ` `        ``while` `(x > ``0``) { ` `            ``x = x >> ``1``; ` `            ``count++; ` `        ``} ` `        ``return` `count; ` `    ``} ` ` `  `    ``// Returns true if n is Bleak ` `    ``static` `boolean` `isBleak(``int` `n) ` `    ``{ ` `        ``// Check for all numbers 'x' smaller ` `        ``// than n. If x + countSetBits(x) ` `        ``// becomes n, then n can't be Bleak ` `        ``for` `(``int` `x = n - ceilLog2(n); x < n; x++) ` `            ``if` `(x + countSetBits(x) == n) ` `                ``return` `false``; ` ` `  `        ``return` `true``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``if` `(isBleak(``3``)) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` ` `  `        ``if` `(isBleak(``4``)) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` `    ``} ` `} ` `// This code is contributed by Prerna Saini `

## Python3

 `# An efficient Python 3 program ` `# to check Bleak Number ` `import` `math ` ` `  `# Function to get no of set ` `# bits in binary representation ` `# of passed binary no. ` `def` `countSetBits(x) : ` `     `  `    ``count ``=` `0` `     `  `    ``while` `(x) : ` `        ``x ``=` `x & (x ``-` `1``)  ` `        ``count ``=` `count ``+` `1` `     `  `    ``return` `count ` `     `  `# A function to return ceiling ` `# of log x in base 2. For  ` `# example, it returns 3 for 8  ` `# and 4 for 9. ` `def` `ceilLog2(x) : ` `     `  `    ``count ``=` `0` `    ``x ``=` `x ``-` `1` `     `  `    ``while` `(x > ``0``) : ` `        ``x ``=` `x>>``1` `        ``count ``=` `count ``+` `1` `     `  `    ``return` `count ` `     `  `# Returns true if n is Bleak ` `def` `isBleak(n) : ` `     `  `    ``# Check for all numbers 'x' ` `    ``# smaller than n. If x +  ` `    ``# countSetBits(x) becomes n,  ` `    ``# then n can't be Bleak ` `    ``for` `x ``in` `range` `((n ``-` `ceilLog2(n)), n) : ` `         `  `        ``if` `(x ``+` `countSetBits(x) ``=``=` `n) : ` `            ``return` `False` ` `  `    ``return` `True` ` `  `# Driver code ` `if``(isBleak(``3``)) : ` `    ``print``(``"Yes"``)  ` `else` `: ` `    ``print``( ``"No"``) ` `     `  `if``(isBleak(``4``)) : ` `    ``print``(``"Yes"``) ` `else` `: ` `    ``print``(``"No"``) ` `     `  `# This code is contributed by Nikita Tiwari. `

## C#

 `// An efficient C# program to check ` `// Bleak Number ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``/* Function to get no of set  ` `    ``bits in binary representation ` `    ``of passed binary no. */` `    ``static` `int` `countSetBits(``int` `x) ` `    ``{ ` `        ``int` `count = 0; ` `        ``while` `(x != 0) { ` `            ``x &= (x - 1); ` `            ``count++; ` `        ``} ` `        ``return` `count; ` `    ``} ` ` `  `    ``// A function to return ceiling ` `    ``// of log x in base 2. For  ` `    ``// example, it returns 3 for 8  ` `    ``// and 4 for 9. ` `    ``static` `int` `ceilLog2(``int` `x) ` `    ``{ ` `        ``int` `count = 0; ` `        ``x--; ` `        ``while` `(x > 0) { ` `            ``x = x >> 1; ` `            ``count++; ` `        ``} ` `        ``return` `count; ` `    ``} ` ` `  `    ``// Returns true if n is Bleak ` `    ``static` `bool` `isBleak(``int` `n) ` `    ``{ ` `         `  `        ``// Check for all numbers  ` `        ``// 'x' smaller than n. If ` `        ``// x + countSetBits(x) ` `        ``// becomes n, then n  ` `        ``// can't be Bleak ` `        ``for` `(``int` `x = n - ceilLog2(n);  ` `                          ``x < n; x++) ` `            ``if` `(x + countSetBits(x)  ` `                               ``== n) ` `                ``return` `false``; ` ` `  `        ``return` `true``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``if` `(isBleak(3)) ` `            ``Console.WriteLine(``"Yes"``); ` `        ``else` `            ``Console.WriteLine(``"No"``); ` ` `  `        ``if` `(isBleak(4)) ` `            ``Console.WriteLine(``"Yes"``); ` `        ``else` `            ``Console.WriteLine(``"No"``); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` 0)  ` `    ``{ ` `        ``\$x` `= ``\$x` `>> 1; ` `        ``\$count``++; ` `    ``} ` `    ``return` `\$count``; ` `} ` ` `  `// Returns true if n is Bleak ` `function` `isBleak( ``\$n``) ` `{ ` `     `  `    ``// Check for all numbers 'x' smaller ` `    ``// than n. If x + countSetBits(x) ` `    ``// becomes n, then n can't be Bleak ` `    ``for` `(``\$x` `= ``\$n` `- ceilLog2(``\$n``); ``\$x` `< ``\$n``; ``\$x``++) ` `        ``if` `(``\$x` `+ countSetBits(``\$x``) == ``\$n``) ` `            ``return` `false; ` ` `  `    ``return` `true; ` `} ` ` `  `    ``// Driver code ` `    ``if``(isBleak(3)) ` `        ``echo` ```"Yes "``` `; ` `     `  `    ``else` `        ``echo` ```"No "````; ` `     `  `    ``if``(isBleak(4)) ` `        ``echo` ```"Yes "``` `; ` `     `  `    ``else` `        ``echo` ```"No "````; ` `         `  `// This code is contributed by anuj_67 ` `?> `

Output :

```No
Yes```

Time Complexity: O(Log n * Log n)

Note: In GCC, we can directly count set bits using __builtin_popcount(). So we can avoid a separate function for counting set bits.

 `// C++ program to demonstrate __builtin_popcount() ` `#include ` `using` `namespace` `std; ` ` `  `int` `main() ` `{ ` `    ``cout << __builtin_popcount(4) << endl; ` `    ``cout << __builtin_popcount(15); ` ` `  `    ``return` `0; ` `} `

Output :

```1
4```

This article is attributed to GeeksforGeeks.org

code

load comments