Un número ‘n’ se llama Bleak si no se puede representar como la suma de un número positivo x y establecer el número de bits en x, es decir, x + countSetBits(x) no es igual a n para ningún número x no negativo.
Ejemplos:
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.
Método 1 (Simple)
bool isBleak(n)
1) Consider all numbers smaller than n
a) If x + countSetBits(x) == n
return false
2) Return true
A continuación se muestra la implementación del enfoque simple.
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>
Producción :
No Yes
La complejidad temporal de la solución anterior es O(n Log n).
Espacio auxiliar: O(1)
Método 2 (eficiente)
La idea se basa en el hecho de que la mayor cantidad de bits establecidos en cualquier número menor que n no puede exceder el techo de Log 2 n. Por lo tanto, debemos verificar solo los números del rango n – ceilingLog2(n) a 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
A continuación se muestra la implementación de la 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>
Producción:
No Yes
Complejidad de tiempo: O (Iniciar sesión n * Iniciar sesión n)
Espacio auxiliar: O(1)
Nota: En GCC, podemos contar directamente los bits establecidos usando __builtin_popcount(). Entonces podemos evitar una función separada para contar bits establecidos.
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>
Producción :
1 4
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Rahuain . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA