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 <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 Bleakbool 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 codeint main(){ isBleak(3) ? cout << "Yes\n" : cout << "No\n"; isBleak(4) ? cout << "Yes\n" : cout << "No\n"; return 0;} |
Java
// A simple Java program to check Bleak Numberimport 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.*/ |
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 Bleakdef 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 codeif(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 Numberusing 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
<?php// A simple PHP program// to check Bleak Number// Function to get no of// set bits in binary// representation of// passed binary no.function countSetBits( $x){ $count = 0; while ($x) { $x &= ($x - 1); $count++; } return $count;}// Returns true if n is Bleakfunction isBleak( $n){ // Check for all numbers 'x' smaller // than n. If x + countSetBits(x) // becomes n, then n can't be Bleak for($x = 1; $x < $n; $x++) if ($x + countSetBits($x) == $n) return false; return true;} // Driver code if(isBleak(3)) echo "Yes\n" ; else echo "No\n"; if(isBleak(4)) echo "Yes\n" ; else echo "No\n"; // This code is contributed by anuj_67.?> |
Javascript
<script>// JavaScript program to check Bleak Number /* Function to get no of set bits in binary representation of passed binary no. */ function countSetBits(x) { let count = 0; while (x != 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 (let x = 1; x < n; x++) if (x + countSetBits(x) == n) return false; return true; } // Driver Code if (isBleak(3)) document.write("Yes" + "<br/>"); else document.write("No" + "<br/>"); if (isBleak(4)) document.write("Yes" + "<br/>"); else document.write("No" + "<br/>");</script> |
Output :
No Yes
Time complexity of above solution is O(n Log n).
Auxiliary Space: O(1)
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 <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;}// 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 Bleakbool 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 codeint main(){ isBleak(3) ? cout << "Yes\n" : cout << "No\n"; isBleak(4) ? cout << "Yes\n" : cout << "No\n"; return 0;} |
Java
// An efficient Java program to// check Bleak Numberimport 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 Numberimport 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 Bleakdef 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 codeif(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 Numberusing 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
<?php// An efficient PHP program// to check Bleak Number/* Function to get no of set bits in binary representation of passed binary no. */function countSetBits( $x){ $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.function ceilLog2( $x){ $count = 0; $x--; while ($x > 0) { $x = $x >> 1; $count++; } return $count;}// Returns true if n is Bleakfunction 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\n" ; else echo "No\n"; if(isBleak(4)) echo "Yes\n" ; else echo "No\n"; // This code is contributed by anuj_67?> |
Javascript
<script> // An efficient JavaScript // program to check Bleak Number /* Function to get no of set bits in binary representation of passed binary no. */ function countSetBits(x) { let 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. function ceilLog2(x) { let count = 0; x--; while (x > 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 (let x = n - ceilLog2(n); x < n; x++) if (x + countSetBits(x) == n) return false; return true; } if (isBleak(3)) document.write("Yes" + "</br>"); else document.write("No" + "</br>"); if (isBleak(4)) document.write("Yes" + "</br>"); else document.write("No" + "</br>"); </script> |
Output:
No Yes
Time Complexity: O(Log n * Log n)
Auxiliary Space: O(1)
Note: In GCC, we can directly count set bits using __builtin_popcount(). So we can avoid a separate function for counting set bits.
CPP
// C++ program to demonstrate __builtin_popcount()#include <iostream>using namespace std;int main(){ cout << __builtin_popcount(4) << endl; cout << __builtin_popcount(15); return 0;} |
Java
// Java program to demonstrate Integer.bitCount()import java.util.*;class GFG{public static void main(String[] args){ System.out.print(Integer.bitCount(4) +"\n"); System.out.print(Integer.bitCount(15));}}// This code is contributed by umadevi9616 |
Python3
# Python program to demonstrate Integer.bitCount()def bitsoncount(i): assert 0 <= i < 0x100000000 i = i - ((i >> 1) & 0x55555555) i = (i & 0x33333333) + ((i >> 2) & 0x33333333) return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24# Driver codeif __name__ == '__main__': x = 4; y = 15; print(bitsoncount(x)); print(bitsoncount(y));# This code is contributed by umadevi9616 |
C#
// C# program to demonstrate int.bitCount()using System;public class GFG{public static int bitCount (int n) { n = n - ((n >> 1) & 0x55555555); n = (n & 0x33333333) + ((n >> 2) & 0x33333333); return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; }public static void Main(String[] args){ Console.WriteLine(bitCount(4)); Console.WriteLine(bitCount(15));}}// This code is contributed by gauravrajput1 |
Javascript
<script> // javascript program to demonstrate int.bitCount()function bitCount ( n) { n = n - ((n >> 1) & 0x55555555); n = (n & 0x33333333) + ((n >> 2) & 0x33333333); return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; } document.write(bitCount(4)+"<br/>"); document.write(bitCount(15));// This code is contributed by gauravrajput1</script> |
Output :
1 4
Time Complexity: O(log n)
Auxiliary Space: O(1)
This article is contributed by Rahuain. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
