Skip to main content

Check if a number is bleak

In this article, we will explore the concept of "bleak numbers" and how to determine whether a given number is bleak or not. A number is said to be bleak if it cannot be represented as the sum of any number and the count of active (1) bits in that number. To understand this, let's break down the problem and provide a step-by-step explanation, along with suitable examples.

Understanding the Problem

A "bleak number" is a positive integer that cannot be represented as the sum of any positive integer and the count of active bits (1s) in that integer. For example, if we consider the number 5, it has two active bits (binary representation: 101), and it cannot be represented as the sum of any positive integer and the count of active bits (1s) in that integer. So, 5 is a bleak number.

Algorithm and Pseudocode

Here is the pseudocode representation of the algorithm: 

// Returns the number of all active bits in n
function countActiveBit(n):
    num = n
    count = 0
    // Count active bits
    while num > 0:
        count = count + 1
        num = num AND (num - 1)
    return count

// Determine that given number is bleak number or not
function isBleak(num):
    for i = 1 to num - 1:
        if (countActiveBit(i) + i) == num:
            // When [i] and sum of active bits is equal to given number
            print num, "is not a bleak number"
            return
    print num, "is a bleak number"

To determine if a given number is bleak or not, we will use the following algorithm:

  1. Define a function countActiveBit(n) to calculate the number of active (1) bits in a given number n.
  2. Define a function isBleak(num) to check if the number num is bleak or not.
  3. Iterate through all numbers from 1 to num - 1.
  4. For each number i, calculate the sum of i and the count of active bits in i.
  5. If the sum is equal to num, then num is not a bleak number, and we can return from the function.
  6. If no such number is found in the loop, then num is a bleak number.

Program Solution

// C Program 
// Check if a number is bleak
#include <stdio.h>

// Returns the number of all active bits in n
int countActiveBit(int n)
{
	int num = n;
	int count = 0;
	// Count active bits
	while (num > 0)
	{
		count++;
		num = num & (num - 1);
	}
	return count;
}
// Determine that given number is bleak number or not
void isBleak(int num)
{
	for (int i = 1; i < num; ++i)
	{
		if ((countActiveBit(i) + i) == num)
		{
			// When [i] and sum of active bits is equal to given number
			printf(" %d is not bleak number\n", num);
			return;
		}
	}
	printf(" %d Is an bleak number\n", num);
}
int main(int argc, char const *argv[])
{
	// Test Cases
	isBleak(13);
	isBleak(27);
	isBleak(39);
	isBleak(14);
	isBleak(21);
	return 0;
}

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
/*
  Java Program 
  Check if a number is bleak
*/
public class BleakNumber
{
	// Returns the number of all active bits in n
	public int countActiveBit(int n)
	{
		int num = n;
		int count = 0;
		// Count active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		return count;
	}
	// Determine that given number is bleak number or not
	public void isBleak(int num)
	{
		for (int i = 1; i < num; ++i)
		{
			if ((countActiveBit(i) + i) == num)
			{
				// When [i] and sum of active bits is equal to given number
				System.out.print(" " + num + " is not bleak number\n");
				return;
			}
		}
		System.out.print(" " + num + " Is an bleak number\n");
	}
	public static void main(String[] args)
	{
		BleakNumber task = new BleakNumber();
		// Test Cases
		task.isBleak(13);
		task.isBleak(27);
		task.isBleak(39);
		task.isBleak(14);
		task.isBleak(21);
	}
}

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
// Include header file
#include <iostream>
using namespace std;

/*
  C++ Program 
  Check if a number is bleak
*/

class BleakNumber
{
	public:
		// Returns the number of all active bits in n
		int countActiveBit(int n)
		{
			int num = n;
			int count = 0;
			// Count active bits
			while (num > 0)
			{
				count++;
				num = num &(num - 1);
			}
			return count;
		}
	// Determine that given number is bleak number or not
	void isBleak(int num)
	{
		for (int i = 1; i < num; ++i)
		{
			if ((this->countActiveBit(i) + i) == num)
			{
				// When [i] and sum of active bits is equal to given number
				cout << " " << num << " is not bleak number\n";
				return;
			}
		}
		cout << " " << num << " Is an bleak number\n";
	}
};
int main()
{
	BleakNumber task = BleakNumber();
	// Test Cases
	task.isBleak(13);
	task.isBleak(27);
	task.isBleak(39);
	task.isBleak(14);
	task.isBleak(21);
	return 0;
}

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
// Include namespace system
using System;
/*
  C# Program 
  Check if a number is bleak
*/
public class BleakNumber
{
	// Returns the number of all active bits in n
	public int countActiveBit(int n)
	{
		int num = n;
		int count = 0;
		// Count active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		return count;
	}
	// Determine that given number is bleak number or not
	public void isBleak(int num)
	{
		for (int i = 1; i < num; ++i)
		{
			if ((countActiveBit(i) + i) == num)
			{
				// When [i] and sum of active bits is equal to given number
				Console.Write(" " + num + " is not bleak number\n");
				return;
			}
		}
		Console.Write(" " + num + " Is an bleak number\n");
	}
	public static void Main(String[] args)
	{
		BleakNumber task = new BleakNumber();
		// Test Cases
		task.isBleak(13);
		task.isBleak(27);
		task.isBleak(39);
		task.isBleak(14);
		task.isBleak(21);
	}
}

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
<?php
/*
  Php Program 
  Check if a number is bleak
*/
class BleakNumber
{
	// Returns the number of all active bits in n
	public	function countActiveBit($n)
	{
		$num = $n;
		$count = 0;
		// Count active bits
		while ($num > 0)
		{
			$count++;
			$num = $num & ($num - 1);
		}
		return $count;
	}
	// Determine that given number is bleak number or not
	public	function isBleak($num)
	{
		for ($i = 1; $i < $num; ++$i)
		{
			if (($this->countActiveBit($i) + $i) == $num)
			{
				// When [i] and sum of active bits is equal to given number
				echo " ". $num ." is not bleak number\n";
				return;
			}
		}
		echo " ". $num ." Is an bleak number\n";
	}
}

function main()
{
	$task = new BleakNumber();
	// Test Cases
	$task->isBleak(13);
	$task->isBleak(27);
	$task->isBleak(39);
	$task->isBleak(14);
	$task->isBleak(21);
}
main();

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
/*
  Node Js Program 
  Check if a number is bleak
*/
class BleakNumber
{
	// Returns the number of all active bits in n
	countActiveBit(n)
	{
		var num = n;
		var count = 0;
		// Count active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		return count;
	}
	// Determine that given number is bleak number or not
	isBleak(num)
	{
		for (var i = 1; i < num; ++i)
		{
			if ((this.countActiveBit(i) + i) == num)
			{
				// When [i] and sum of active bits is equal to given number
				process.stdout.write(" " + num + " is not bleak number\n");
				return;
			}
		}
		process.stdout.write(" " + num + " Is an bleak number\n");
	}
}

function main()
{
	var task = new BleakNumber();
	// Test Cases
	task.isBleak(13);
	task.isBleak(27);
	task.isBleak(39);
	task.isBleak(14);
	task.isBleak(21);
}
main();

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
#   Python 3 Program 
#   Check if a number is bleak

class BleakNumber :
	#  Returns the number of all active bits in n
	def countActiveBit(self, n) :
		num = n
		count = 0
		#  Count active bits
		while (num > 0) :
			count += 1
			num = num & (num - 1)
		
		return count
	
	#  Determine that given number is bleak number or not
	def isBleak(self, num) :
		i = 1
		while (i < num) :
			if ((self.countActiveBit(i) + i) == num) :
				#  When [i] and sum of active bits is equal to given number
				print(" ", num ," is not bleak number")
				return
			
			i += 1
		
		print(" ", num ," Is an bleak number")
	

def main() :
	task = BleakNumber()
	#  Test Cases
	task.isBleak(13)
	task.isBleak(27)
	task.isBleak(39)
	task.isBleak(14)
	task.isBleak(21)

if __name__ == "__main__": main()

Output

  13  Is an bleak number
  27  is not bleak number
  39  Is an bleak number
  14  is not bleak number
  21  Is an bleak number
#   Ruby Program 
#   Check if a number is bleak

class BleakNumber 
	#  Returns the number of all active bits in n
	def countActiveBit(n) 
		num = n
		count = 0
		#  Count active bits
		while (num > 0) 
			count += 1
			num = num & (num - 1)
		end

		return count
	end

	#  Determine that given number is bleak number or not
	def isBleak(num) 
		i = 1
		while (i < num) 
			if ((self.countActiveBit(i) + i) == num) 
				#  When [i] and sum of active bits is equal to given number
				print(" ", num ," is not bleak number\n")
				return
			end

			i += 1
		end

		print(" ", num ," Is an bleak number\n")
	end

end

def main() 
	task = BleakNumber.new()
	#  Test Cases
	task.isBleak(13)
	task.isBleak(27)
	task.isBleak(39)
	task.isBleak(14)
	task.isBleak(21)
end

main()

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number

/*
  Scala Program 
  Check if a number is bleak
*/
class BleakNumber
{
	// Returns the number of all active bits in n
	def countActiveBit(n: Int): Int = {
		var num: Int = n;
		var count: Int = 0;
		// Count active bits
		while (num > 0)
		{
			count += 1;
			num = num & (num - 1);
		}
		return count;
	}
	// Determine that given number is bleak number or not
	def isBleak(num: Int): Unit = {
		var i: Int = 1;
		while (i < num)
		{
			if ((this.countActiveBit(i) + i) == num)
			{
				// When [i] and sum of active bits is equal to given number
				print(" " + num + " is not bleak number\n");
				return;
			}
			i += 1;
		}
		print(" " + num + " Is an bleak number\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BleakNumber = new BleakNumber();
		// Test Cases
		task.isBleak(13);
		task.isBleak(27);
		task.isBleak(39);
		task.isBleak(14);
		task.isBleak(21);
	}
}

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
/*
  Swift 4 Program 
  Check if a number is bleak
*/
class BleakNumber
{
	// Returns the number of all active bits in n
	func countActiveBit(_ n: Int)->Int
	{
		var num: Int = n;
		var count: Int = 0;
		// Count active bits
		while (num > 0)
		{
			count += 1;
			num = num & (num - 1);
		}
		return count;
	}
	// Determine that given number is bleak number or not
	func isBleak(_ num: Int)
	{
		var i: Int = 1;
		while (i < num)
		{
			if ((self.countActiveBit(i) + i) == num)
			{
				// When [i] and sum of active bits is equal to given number
				print(" ", num ," is not bleak number");
				return;
			}
			i += 1;
		}
		print(" ", num ," Is an bleak number");
	}
}
func main()
{
	let task: BleakNumber = BleakNumber();
	// Test Cases
	task.isBleak(13);
	task.isBleak(27);
	task.isBleak(39);
	task.isBleak(14);
	task.isBleak(21);
}
main();

Output

  13  Is an bleak number
  27  is not bleak number
  39  Is an bleak number
  14  is not bleak number
  21  Is an bleak number
/*
  Kotlin Program 
  Check if a number is bleak
*/
class BleakNumber
{
	// Returns the number of all active bits in n
	fun countActiveBit(n: Int): Int
	{
		var num: Int = n;
		var count: Int = 0;
		// Count active bits
		while (num > 0)
		{
			count += 1;
			num = num and(num - 1);
		}
		return count;
	}
	// Determine that given number is bleak number or not
	fun isBleak(num: Int): Unit
	{
		var i: Int = 1;
		while (i < num)
		{
			if ((this.countActiveBit(i) + i) == num)
			{
				// When [i] and sum of active bits is equal to given number
				print(" " + num + " is not bleak number\n");
				return;
			}
			i += 1;
		}
		print(" " + num + " Is an bleak number\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: BleakNumber = BleakNumber();
	// Test Cases
	task.isBleak(13);
	task.isBleak(27);
	task.isBleak(39);
	task.isBleak(14);
	task.isBleak(21);
}

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number
// Rust Program 
// Check if a number is bleak
fn main()
{
	// Test Cases
	is_bleak(13);
	is_bleak(27);
	is_bleak(39);
	is_bleak(14);
	is_bleak(21);
}
fn is_bleak(num: i32)
{
	let mut i: i32 = 1;
	while i < num
	{
		if (count_active_bit(i) + i) == num
		{
			// When [i] and sum of active bits is equal to given number
			print!(" {} is not bleak number\n", num);
			return;
		}
		i += 1;
	}
	print!(" {} Is an bleak number\n", num);
}
fn count_active_bit(n: i32)->i32
{
	let mut num: i32 = n;
	let mut count: i32 = 0;
	// Count active bits
	while num > 0
	{
		count = count + 1;
		num = num & (num - 1);
	}
	return count;
}

Output

 13 Is an bleak number
 27 is not bleak number
 39 Is an bleak number
 14 is not bleak number
 21 Is an bleak number

Example and Output

Let's consider a few test cases to understand the output of our algorithm: 


isBleak(13) // Output: 13 is a bleak number
isBleak(27) // Output: 27 is not a bleak number
isBleak(39) // Output: 39 is a bleak number
isBleak(14) // Output: 14 is not a bleak number
isBleak(21) // Output: 21 is a bleak number

Explanation of the Output:

  • isBleak(13): The binary representation of 13 is 1101, which has three active bits. We can't find any number less than 13 such that their sum and the count of active bits equals 13. So, 13 is a bleak number.
  • isBleak(27): The binary representation of 27 is 11011, which has five active bits. By checking all numbers less than 27, we find that 22 (binary: 10110) + 4 (active bits) = 26, not equal to 27. So, 27 is not a bleak number.
  • isBleak(39): The binary representation of 39 is 100111, which has four active bits. We can't find any number less than 39 such that their sum and the count of active bits equals 39. Thus, 39 is a bleak number.
  • isBleak(14): The binary representation of 14 is 1110, which has three active bits. We find that 10 (binary: 1010) + 2 (active bits) = 12, not equal to 14. Hence, 14 is not a bleak number.
  • isBleak(21): The binary representation of 21 is 10101, which has three active bits. We can't find any number less than 21 such that their sum and the count of active bits equals 21. Therefore, 21 is a bleak number.

Time Complexity

The time complexity of our algorithm mainly depends on the isBleak(num) function, which checks all numbers from 1 to num - 1. The countActiveBit(n) function, which calculates the number of active bits in n, runs in O(log n) time complexity due to the bitwise operations. Since we are iterating through all numbers from 1 to num - 1, the overall time complexity of the algorithm is O(num * log(num)). In the worst case, the algorithm will have to check all numbers up to the given number num, leading to linear time complexity.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment