Dado un número entero no negativo N, la tarea es encontrar el número de números enteros no negativos
menores o iguales a N cuyo OR bit a bit y la suma con N sean iguales.
Ejemplos:
Input : N = 3 Output : 1 0 is the only number in [0, 3] that satisfies given property. (0 + 3) = (0 | 3) Input : 10 Output : 4 (0 + 10) = (0 | 10) (Both are 10) (1 + 10) = (1 | 10) (Both are 11) (4 + 10) = (4 | 10) (Both are 14) (5 + 10) = (5 | 10) (Both are 15)
Una solución simple es atravesar todos los números de 0 a N y hacer OR bit a bit y SUMA con N, si ambos son contadores de incrementos iguales.
Complejidad del tiempo = O(N).
Una solución eficiente es seguir los siguientes pasos.
1. Encuentre el recuento de bits cero en N.
2. Devuelva pow(2,count).
La idea se basa en el hecho de que el OR bit a bit y la suma de un número x con N son iguales, si y solo si
el AND bit a bit de x con N será 0
Let, N=10 =10102. Bitwise AND of a number with N will be 0, if number contains zero bit with all respective set bit(s) of N and either zero bit or set bit with all respective zero bit(s) of N (because, 0&0=1&0=0). e.g. bit : 1 0 1 0 position: 4 3 2 1 Bitwise AND of any number with N will be 0, if the number has following bit pattern 1st position can be either 0 or 1 (2 ways) 2nd position can be 1 (1 way) 3rd position can be either 0 or 1 (2 ways) 4th position can be 1 (1 way) Total count = 2*1*2*1 = 22 = 4.
C++
// C++ program to count numbers whose bitwise // OR and sum with N are equal #include <bits/stdc++.h> using namespace std; // Function to find total 0 bit in a number unsigned int CountZeroBit(int n) { unsigned int count = 0; while(n) { if (!(n & 1)) count++; n >>= 1; } return count; } // Function to find Count of non-negative numbers // less than or equal to N, whose bitwise OR and // SUM with N are equal. int CountORandSumEqual(int N ) { // count number of zero bit in N int count = CountZeroBit(N); // power of 2 to count return (1 << count); } // Driver code int main() { int N = 10; cout << CountORandSumEqual(N); return 0; }
Java
// Java program to count numbers whose bitwise // OR and sum with N are equal class GFG { // Function to find total 0 bit in a number static int CountZeroBit(int n) { int count = 0; while(n > 0) { if ((n & 1) != 0) count++; n >>= 1; } return count; } // Function to find Count of non-negative // numbers less than or equal to N, whose // bitwise OR and SUM with N are equal. static int CountORandSumEqual(int N ) { // count number of zero bit in N int count = CountZeroBit(N); // power of 2 to count return (1 << count); } //Driver code public static void main (String[] args) { int N = 10; System.out.print(CountORandSumEqual(N)); } } // This code is contributed by Anant Agarwal.
Python3
# Python3 program to count numbers whose # bitwise OR and sum with N are equal # Function to find total 0 bit in a number def CountZeroBit(n): count = 0 while(n): if (not(n & 1)): count += 1 n >>= 1 return count # Function to find Count of non-negative # numbers less than or equal to N, whose # bitwise OR and SUM with N are equal. def CountORandSumEqual(N): # count number of zero bit in N count = CountZeroBit(N) # power of 2 to count return (1 << count) # Driver code N = 10 print(CountORandSumEqual(N)) # This code is contributed by Anant Agarwal.
C#
// C# program to count numbers whose // bitwise OR and sum with N are equal using System; class GFG { // Function to find total // 0 bit in a number static int CountZeroBit(int n) { int count = 0; while(n>0) { if (n%2!=0) count++; n >>= 1; } return count; } // Function to find Count of non-negative // numbers less than or equal to N, whose // bitwise OR and SUM with N are equal. static int CountORandSumEqual(int N ) { // count number of zero bit in N int count = CountZeroBit(N); // power of 2 to count return (1 << count); } //Driver code public static void Main() { int N = 10; Console.Write(CountORandSumEqual(N)); } } // This code is contributed by Anant Agarwal.
PHP
<?php // PHP program to count // numbers whose bitwise // OR and sum with N are equal // Function to find total // 0 bit in a number function CountZeroBit($n) { $count = 0; while($n) { if (!($n & 1)) $count++; $n >>= 1; } return $count; } // Function to find Count of // non-negative numbers less // than or equal to N, whose // bitwise OR and SUM with N // are equal. function CountORandSumEqual($N ) { // count number of // zero bit in N $count = CountZeroBit($N); // power of 2 to count return (1 << $count); } // Driver code $N = 10; echo CountORandSumEqual($N); // This code is contributed by Ajit ?>
Javascript
<script> // Javascript program to count numbers whose // bitwise OR and sum with N are equal // Function to find total // 0 bit in a number function CountZeroBit(n) { let count = 0; while(n>0) { if (n%2!=0) count++; n >>= 1; } return count; } // Function to find Count of non-negative // numbers less than or equal to N, whose // bitwise OR and SUM with N are equal. function CountORandSumEqual(N) { // count number of zero bit in N let count = CountZeroBit(N); // power of 2 to count return (1 << count); } let N = 10; document.write(CountORandSumEqual(N)); </script>
Producción :
4
Complejidad de tiempo total: O(log 2 (N))
Espacio Auxiliar: O(1)
Este artículo es una contribución de Viranjan Kumar Akela . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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