# Check if a number is Bleak

A number ‘n’ is called Bleak number 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) which is 2 + 1.  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.`

Source : SAP Lab Interview

We strongly recommend you to minimize your browser and try this yourself first.

Below is one simple solution.

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

Below is C++ implementation of the simple approach.

`// C++ program to find if a number is Bleak #include <bits/stdc++.h> 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/n" : cout << "No/n";   isBleak(4)? cout << "Yes/n" : cout << "No/n";   return 0; }`

Output :

`No Yes`

Time complexity of above solution is O(n Log n). Can there be a better solution, please comment.