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:
- Define a function
countActiveBit(n)
to calculate the number of active (1) bits in a given numbern
. - Define a function
isBleak(num)
to check if the numbernum
is bleak or not. - Iterate through all numbers from 1 to
num - 1
. - For each number
i
, calculate the sum ofi
and the count of active bits ini
. - If the sum is equal to
num
, thennum
is not a bleak number, and we can return from the function. - 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.
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