Dado un entero n , la tarea es encontrar el número de valores posibles de 0 ≤ x ≤ n que satisfacen n XOR x = n – x .
Ejemplos:
Entrada: n = 5
Salida: 4 Los
siguientes valores de x satisfacen la ecuación
5 XOR 0 = 5 – 0 = 5
5 XOR 1 = 5 – 1 = 4
5 XOR 4 = 5 – 4 = 1
5 XOR 5 = 5 – 5 = 0Entrada: n = 2
Salida: 2
Enfoque ingenuo: el enfoque sencillo es verificar todos los valores de 0 a n (ambos inclusive) y encontrar si satisfacen la ecuación. El siguiente código implementa este enfoque:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the count of
// valid values of x
static int countX(int n)
{
int count = 0;
for (int i = 0; i <= n; i++)
{
// If n - x = n XOR x
if (n - i == (n ^ i))
count++;
}
// Return the required count;
return count;
}
// Driver code
int main()
{
int n = 5;
int answer = countX(n);
cout << answer;
}
// This code is contributed by
// Shivi_Aggarwal
Java
// Java implementation of the approach
public class GFG {
// Function to return the count of
// valid values of x
static int countX(int n)
{
int count = 0;
for (int i = 0; i <= n; i++) {
// If n - x = n XOR x
if (n - i == (n ^ i))
count++;
}
// Return the required count;
return count;
}
// Driver code
public static void main(String args[])
{
int n = 5;
int answer = countX(n);
System.out.println(answer);
}
}
Python3
# Python3 implementation of the approach import math as mt # Function to return the count of # valid values of x def countX(n): count = 0 for i in range(n + 1): if n - i == (n ^ i): count += 1 return count # Driver Code if __name__ == '__main__': n = 5 answer = countX(n) print(answer) # This code is contributed by # Mohit kumar 29
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the count of
// valid values of x
static int countX(int n)
{
int count = 0;
for (int i = 0; i <= n; i++)
{
// If n - x = n XOR x
if (n - i == (n ^ i))
count++;
}
// Return the required count;
return count;
}
// Driver code
public static void Main()
{
int n = 5;
int answer = countX(n);
Console.WriteLine(answer);
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return the count of
// valid values of x
function countX($n)
{
$count = 0;
for ($i = 0; $i <= $n; $i++)
{
// If n - x = n XOR x
if ($n - $i == ($n ^ $i))
$count++;
}
// Return the required count;
return $count;
}
// Driver code
$n = 5;
$answer = countX($n);
echo($answer);
// This code is Contributed
// by Mukul Singh.
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of
// valid values of x
function countX(n)
{
let count = 0;
for (let i = 0; i <= n; i++)
{
// If n - x = n XOR x
if (n - i == (n ^ i))
count++;
}
// Return the required count;
return count;
}
// Driver code
let n = 5;
let answer = countX(n);
document.write(answer);
</script>
Producción:
4
Complejidad del tiempo: O(N)
Enfoque eficiente: convertir n a su representación binaria. Ahora, por cada 1 en la string binaria, ya sea que le restemos 1 o 0 , será equivalente a XOR de 1 con 0 o 1, es decir
(1 – 1) = (1 XOR 1) = 0
(1 – 0) = (1 XOR 0) = 1
Pero 0 no satisface esta condición. Entonces, solo necesitamos considerar todos los que están en la representación binaria de n . Ahora, por cada 1 hay dos posibilidades, 0 o 1 . Por lo tanto, si tenemos m número de 1 en n , nuestra solución sería 2 m .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the count of
// valid values of x
int countX(int n)
{
// Convert n into binary String
string binary = bitset<8>(n).to_string();
// To store the count of 1s
int count = 0;
for (int i = 0; i < binary.length(); i++)
{
// If current bit is 1
if (binary.at(i) == '1')
count++;
}
// Calculating answer
int answer = (int)pow(2, count);
return answer;
}
// Driver code
int main()
{
int n = 5;
int answer = countX(n);
cout << (answer);
}
// This code is contributed by Rajput-Ji
Java
// Java implementation of the approach
public class GFG {
// Function to return the count of
// valid values of x
static int countX(int n)
{
// Convert n into binary String
String binary = Integer.toBinaryString(n);
// To store the count of 1s
int count = 0;
for (int i = 0; i < binary.length(); i++) {
// If current bit is 1
if (binary.charAt(i) == '1')
count++;
}
// Calculating answer
int answer = (int)Math.pow(2, count);
return answer;
}
// Driver code
public static void main(String args[])
{
int n = 5;
int answer = countX(n);
System.out.println(answer);
}
}
Python3
# Python3 implementation of the approach
# Function to return the count of
# valid values of x
def countX(n):
# Convert n into binary String
binary = "{0:b}".format(n)
# To store the count of 1s
count = 0
for i in range(len(binary)):
# If current bit is 1
if (binary[i] == '1'):
count += 1
# Calculating answer
answer = int(pow(2, count))
return answer
# Driver code
if __name__ == "__main__":
n = 5
answer = countX(n)
print(answer)
# This code is contributed by ita_c
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of
// valid values of x
static int countX(int n)
{
// Convert n into binary String
string binary = Convert.ToString(n, 2);
// To store the count of 1s
int count = 0;
for (int i = 0; i < binary.Length; i++)
{
// If current bit is 1
if (binary[i] == '1')
count++;
}
// Calculating answer
int answer = (int)Math.Pow(2, count);
return answer;
}
// Driver code
public static void Main()
{
int n = 5;
int answer = countX(n);
Console.WriteLine(answer);
}
}
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of
// valid values of x
function countX(n)
{
// Convert n into binary String
let binary = (n >>> 0).toString(2);
// To store the count of 1s
let count = 0;
for(let i = 0; i < binary.length; i++)
{
// If current bit is 1
if (binary[i] == '1')
count++;
}
// Calculating answer
let answer = Math.floor(Math.pow(2, count));
return answer;
}
// Driver code
let n = 5;
let answer = countX(n);
document.write(answer);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
4
Complejidad del tiempo: 