Número de soluciones de n = x + n ⊕ x

Dado un número n, tenemos que encontrar el número de valores posibles de X tales que n = x + n ⊕ x. Aquí ⊕ representa XOR

Ejemplos:  

Input : n = 3
Output : 4
The possible values of x are 0, 1, 2, and 3.

Input : n = 2
Output : 2
The possible values of x are 0 and 2.

Enfoque de fuerza bruta : podemos ver que x siempre es igual o menor que n, por lo que podemos iterar sobre el rango [0, n] y contar la cantidad de valores que satisfacen la condición requerida. La complejidad temporal de este enfoque es O(n).

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of
// solutions of n = n xor x
int numberOfSolutions(int n)
{
    // Counter to store the number
    // of solutions found
    int c = 0;
 
    for (int x = 0; x <= n; ++x)
        if (n == x + n ^ x)
            ++c;
 
    return c;
}
 
// Driver code
int main()
{
    int n = 3;
    cout << numberOfSolutions(n);
    return 0;
}

// Java implementation of above approach
import java.util.*;
import java.lang.*;
 
class GFG
{
// Function to find the number of
// solutions of n = n xor x
static int numberOfSolutions(int n)
{
    // Counter to store the number
    // of solutions found
    int c = 0;
 
    for (int x = 0; x <= n; ++x)
        if (n == x + (n ^ x))
            ++c;
 
    return c;
}
 
// Driver code
public static void main(String args[])
{
    int n = 3;
    System.out.print(numberOfSolutions(n));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

# Python 3 implementation
# of above approach
 
# Function to find the number of
# solutions of n = n xor x
def numberOfSolutions(n):
 
    # Counter to store the number
    # of solutions found
    c = 0
 
    for x in range(n + 1):
        if (n ==( x +( n ^ x))):
            c += 1
 
    return c
 
# Driver code
if __name__ == "__main__":
    n = 3
    print(numberOfSolutions(n))
 
# This code is contributed
# by ChitraNayal

// C# implementation of above approach
using System;
 
class GFG
{
// Function to find the number of
// solutions of n = n xor x
static int numberOfSolutions(int n)
{
    // Counter to store the number
    // of solutions found
    int c = 0;
 
    for (int x = 0; x <= n; ++x)
        if (n == x + (n ^ x))
            ++c;
 
    return c;
}
 
// Driver code
public static void Main()
{
    int n = 3;
    Console.Write(numberOfSolutions(n));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

<?php
// PHP implementation of above approach
 
// Function to find the number of
// solutions of n = n xor x
function numberOfSolutions($n)
{
    // Counter to store the number
    // of solutions found
    $c = 0;
 
    for ($x = 0; $x <= $n; ++$x)
        if ($n == $x + $n ^ $x)
            ++$c;
 
    return $c;
}
 
// Driver code
$n = 3;
echo numberOfSolutions($n);
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

<script>
 
    // Javascript implementation of above approach
     
    // Function to find the number of
    // solutions of n = n xor x
    function numberOfSolutions(n)
    {
         
        // Counter to store the number
        // of solutions found
        let c = 0;
 
        for(let x = 0; x <= n; ++x)
            if (n == x + n ^ x)
                ++c;
 
        return c;
    }
     
    let n = 3;
    document.write(numberOfSolutions(n));
     
    // This code is contributed by divyesh072019.
</script>

4

Complejidad del tiempo : O(n)

Enfoque eficiente : podemos resolver este problema de una manera más eficiente si consideramos n en su forma binaria. Si se establece un bit de n, es decir, 1, entonces podemos deducir que debe haber un bit establecido correspondiente en x o en n ⊕ x (pero no en ambos). Si el bit correspondiente se establece en x, entonces no se establece en n ⊕ x como 1 ⊕ 1 = 0. De lo contrario, el bit se establece en n ⊕ x como 0 ⊕ 1 = 1. Por lo tanto, para cada bit establecido en n, tenemos puede tener un bit activado o un bit desactivado en x. Sin embargo, no podemos tener un bit activado en x correspondiente a un bit desactivado en n. Por esta lógica, el número de soluciones resulta ser 2 elevado a la potencia del número de bits establecidos en n. La complejidad temporal de este enfoque es O(log n). 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of
// solutions of n = n xor x
int numberOfSolutions(int n)
{
    // Number of set bits in n
    int c = 0;
 
    while (n) {
        c += n % 2;
        n /= 2;
    }
 
    // We can also write (1 << c)
    return pow(2, c);
}
 
// Driver code
int main()
{
    int n = 3;
    cout << numberOfSolutions(n);
    return 0;
}

// Java  implementation of above approach
import java.io.*;
 
class GFG {
// Function to find the number of
// solutions of n = n xor x
static int numberOfSolutions(int n)
{
    // Number of set bits in n
    int c = 0;
 
    while (n>0) {
        c += n % 2;
        n /= 2;
    }
 
    // We can also write (1 << c)
    return (int)Math.pow(2, c);
}
 
// Driver code
 
    public static void main (String[] args) {
        int n = 3;
    System.out.println( numberOfSolutions(n));
    }
}
//This code is contributed by anuj_67

# Python3 implementation of above approach
 
# from math lib. import everything
from math import *
 
# Function to find the number of
# solutions of n = n xor x
def numberOfSolutions(n) :
 
    # Number of set bits in n
    c = 0
 
    while(n) :
        c += n % 2
        n //= 2
 
    # We can also write (1 << c)
    return int(pow(2, c))
 
         
# Driver code    
if __name__ == "__main__" :
 
    n = 3
    print(numberOfSolutions(n))
 
# This code is contributed by ANKITRAI1

// C# implementation of above approach
using System;
 
class GFG
{
// Function to find the number of
// solutions of n = n xor x
static int numberOfSolutions(int n)
{
    // Number of set bits in n
    int c = 0;
 
    while (n > 0)
    {
        c += n % 2;
        n /= 2;
    }
 
    // We can also write (1 << c)
    return (int)Math.Pow(2, c);
}
 
// Driver code
public static void Main ()
{
    int n = 3;
    Console.WriteLine(numberOfSolutions(n));
}
}
 
// This code is contributed by anuj_67

<?php
// PHP implementation of above approach
 
// Function to find the number of
// solutions of n = n xor x
function numberOfSolutions($n)
{
    // Number of set bits in n
    $c = 0;
    while ($n)
    {
        $c += $n % 2;
        $n /= 2;
    }
 
    // We can also write (1 << c)
    return pow(2, $c);
}
 
// Driver code
$n = 3;
echo numberOfSolutions($n);
 
// This code is contributed by jit_t
?>

<script>
 
    // Javascript implementation of above approach
 
    // Function to find the number of
    // solutions of n = n xor x
    function numberOfSolutions(n)
    {
        // Number of set bits in n
        let c = 0;
 
        while (n > 0) {
            c += n % 2;
            n = parseInt(n / 2, 10);
        }
 
        // We can also write (1 << c)
        return Math.pow(2, c);
    }
 
    let n = 3;
    document.write(numberOfSolutions(n));
</script>

4

Complejidad de tiempo : O (log n)