Dado un entero ‘x’, encuentra el número de valores de ‘a’ que satisfacen las siguientes condiciones:
- a XOR x > x
- 0 < un < x
Ejemplos:
Input : x = 10
Output : 5
Explanation: For x = 10, following 5 values
of 'a' satisfy the conditions:
1 XOR 10 = 11
4 XOR 10 = 14
5 XOR 10 = 15
6 XOR 10 = 12
7 XOR 10 = 13
Input : x = 2
Output : 1
Explanation: For x=2, we have just one value
1 XOR 2 = 3.
Enfoque ingenuo
Un enfoque simple consiste en comprobar todos los valores de ‘a’ entre 0 y ‘x’ y calcular su XOR con x y comprobar si se cumple la condición 1.
C++
// C++ program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
#include<bits/stdc++.h>
using namespace std;
int countValues(int x)
{
int count = 0;
for (int i=1; i < x; i++)
if ((i ^ x) > x)
count++;
return count;
}
// Driver code
int main()
{
int x = 10;
cout << countValues(x);
return 0;
}
Java
// Java program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
public class XOR
{
static int countValues(int x)
{
int count = 0;
for (int i=1; i < x; i++)
if ((i ^ x) > x)
count++;
return count;
}
public static void main (String[] args)
{
int x = 10;
System.out.println(countValues(x));
}
}
// This code is contributed by Saket Kumar
Python3
# Python3 program to find # count of values whose # XOR with x is greater # than x and values are # smaller than x def countValues(x): count = 0 for i in range(1 ,x): if ((i ^ x) > x): count += 1 return count # Driver code x = 10 print(countValues(x)) # This code is contributed # by Smitha
C#
// C# program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
using System;
class GFG
{
static int countValues(int x)
{
int count = 0;
for (int i = 1; i < x; i++)
if ((i ^ x) > x)
count++;
return count;
}
public static void Main ()
{
int x = 10;
Console.Write(countValues(x));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
function countValues($x)
{
$count = 0;
for ($i = 1; $i < $x; $i++)
if (($i ^ $x) > $x)
$count++;
return $count;
}
// Driver code
$x = 10;
echo countValues($x);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
function countValues(x)
{
let count = 0;
for (let i=1; i < x; i++)
if ((i ^ x) > x)
count++;
return count;
}
// Driver code
let x = 10;
document.write(countValues(x));
</script>
Producción :
5
La complejidad temporal del enfoque anterior es O(x).
Espacio Auxiliar: O(1)
Enfoque
eficiente La solución eficiente radica en la representación binaria del número. Consideramos todos los 0 en representación binaria. Por cada 0 en la i-ésima posición, podemos tener 2 i números menores o iguales ax con mayor XOR.
C++
// C++ program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
#include<bits/stdc++.h>
using namespace std;
int countValues(int x)
{
// Initialize result
int count = 0, n = 1;
// Traversing through all bits of x
while (x != 0)
{
// If current last bit of x is set
// then increment count by n. Here
// n is a power of 2 corresponding
// to position of bit
if (x%2 == 0)
count += n;
// Simultaneously calculate the 2^n
n *= 2;
// Replace x with x/2;
x /= 2;
}
return count;
}
// Driver code
int main()
{
int x = 10;
cout << countValues(x);
return 0;
}
Java
// Java program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
class GFG
{
static int countValues(int x)
{
// Initialize result
int count = 0, n = 1;
// Traversing through all bits of x
while (x != 0)
{
// If current last bit of x is set
// then increment count by n. Here
// n is a power of 2 corresponding
// to position of bit
if (x % 2 == 0)
count += n;
// Simultaneously calculate the 2^n
n *= 2;
// Replace x with x/2;
x /= 2;
}
return count;
}
// Driver code
public static void main (String[] args)
{
int x = 10;
System.out.println(countValues(x));
}
}
// This code is contributed by Saket Kumar
Python3
# Python3 program to find count # of values whose XOR with # x is greater than x and # values are smaller than x def countValues(x): # Initialize result count = 0; n = 1; # Traversing through # all bits of x while (x > 0): # If current last bit # of x is set then # increment count by # n. Here n is a power # of 2 corresponding # to position of bit if (x % 2 == 0): count += n; # Simultaneously # calculate the 2^n n *= 2; # Replace x with x/2; x /= 2; x = int(x); return count; # Driver code x = 10; print(countValues(x)); # This code is contributed # by mits
C#
// C# program to find count of values
// whose XOR with x is greater than x
// and values are smaller than x
using System;
class GFG
{
static int countValues(int x)
{
// Initialize result
int count = 0, n = 1;
// Traversing through all bits of x
while (x != 0)
{
// If current last bit of x is set
// then increment count by n. Here
// n is a power of 2 corresponding
// to position of bit
if (x % 2 == 0)
count += n;
// Simultaneously calculate the 2^n
n *= 2;
// Replace x with x/2;
x /= 2;
}
return count;
}
// Driver code
public static void Main ()
{
int x = 10;
Console.Write(countValues(x));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to find count
// of values whose XOR with
// x is greater than x and
// values are smaller than x
function countValues($x)
{
// Initialize result
$count = 0;
$n = 1;
// Traversing through
// all bits of x
while ($x != 0)
{
// If current last bit
// of x is set then
// increment count by
// n. Here n is a power
// of 2 corresponding
// to position of bit
if ($x % 2 == 0)
$count += $n;
// Simultaneously
// calculate the 2^n
$n *= 2;
// Replace x with x/2;
$x /= 2;
$x = (int)$x;
}
return $count;
}
// Driver code
$x = 10;
echo countValues($x);
// This code is contributed
// by Smitha
?>
Javascript
<script>
// Javascript program to find count of
// values whose XOR with x is greater
// than x and values are smaller than x
function countValues(x)
{
// Initialize result
var count = 0, n = 1;
// Traversing through all bits of x
while (x != 0)
{
// If current last bit of x is set
// then increment count by n. Here
// n is a power of 2 corresponding
// to position of bit
if (x % 2 == 0)
count += n;
// Simultaneously calculate the 2^n
n *= 2;
// Replace x with x/2;
x = parseInt(x / 2);
}
return count;
}
// Driver code
var x = 10;
document.write(countValues(x));
// This code is contributed by Princi Singh
</script>
Producción :
5
Complejidad temporal: O(Log x).
Espacio Auxiliar: O(1)
Este artículo es una contribución de DANISH KALEEM . 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