# 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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
}
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()
{
// Test Cases
}
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() :
#  Test Cases

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()
#  Test Cases
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
}
}``````

#### 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()
{
// Test Cases
}
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
{
// Test Cases
}``````

#### 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.

## 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.