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