Check if a number is Bleak

0 0 10 minutes read

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 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;
}

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.*/

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

<?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 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 = 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 Log₂n. So we need to check only numbers from range n – ceilingLog2(n) to n.

bool isBleak(n)
1) Consider all numbers n - ceiling(Log_{2n) 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 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\n" : cout << "No\n";
    isBleak(4) ? cout << "Yes\n" : cout << "No\n";
    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

<?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 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\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 code
if __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