Cuente distintos valores XOR entre pares usando números en el rango de 1 a N

Dado un número N. La tarea es contar el número de XOR distintos de cualquier par posible utilizando números del 1 al N inclusive.

Ejemplos:

Entrada: N = 3
Salida: 4
Explicación: Los siguientes son todos los pares posibles usando elementos del 1 al N inclusive.
1^1 = 0 
1^2 = 3 
1^3 = 2 
2^2 = 0 
2^3 = 1
3^3 = 0 
Por lo tanto, hay 4 valores XOR distintos posibles.

Entrada: N = 2
Salida: 2

Enfoque: Este problema está basado en la observación. Siga los pasos a continuación para resolver el problema dado. 

• Para N = 1 y N = 2 , la salida requerida es 1 y 2 respectivamente.
• Ahora para N≥3 , hay dos casos posibles:
  • Si N no es una potencia de dos, habrá un total de números ‘t’ donde t es la potencia de 2 que está justo al lado del número N. Varían de [0 a t – 1] . Porque digamos, N = 5 o 6 o 7 En todos los casos anteriores los valores varían de [0, 1, 2, 3, 4, 5, 6, 7] .
  • Si N es una potencia de dos entonces, todos los números serán posibles excepto el propio número. Porque digamos, N = 4 en binario es «100» , así que, como sabemos, la operación XOR da « 1″ si ambos bits son diferentes, de lo contrario da 0 . Los valores posibles son [0, 1, 2, 3,    4 , 5, 6, 7] .

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement above approach
#include <cmath>
#include <iostream>
using namespace std;
 
int findDistinctXOR(int n)
{
 
    // Corner case
    if (n == 1) {
        cout << 1 << endl;
    }
    if (n == 2) {
        cout << 2 << endl;
    }
 
    long long x, next;
    x = log2(n);
 
    // if n is power of two
    if ((n & (n - 1)) == 0) {
 
        next = pow(2, x + 1);
        cout << next - 1 << endl;
    }
    else {
        next = pow(2, x + 1);
        cout << next << endl;
    }
}
 
// Driver Code
int main()
{
    int N = 3;
 
    findDistinctXOR(N);
    return 0;
}

// Java code to implement above approach
//include <cmath>
import java.util.*;
class GFG
{
 
static void findDistinctXOR(int n)
{
 
    // Corner case
    if (n == 1) {
        System.out.print(1 +"\n");
    }
    if (n == 2) {
        System.out.print(2 +"\n");
    }
 
    long x, next;
    x = (long) Math.log(n);
 
    // if n is power of two
    if ((n & (n - 1)) == 0) {
 
        next = (long) Math.pow(2, x + 1);
        System.out.print(next - 1 +"\n");
    }
    else {
        next = (long) Math.pow(2, x + 1);
        System.out.print(next +"\n");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
 
    findDistinctXOR(N);
}
}
 
// This code is contributed by 29AjayKumar

# Python code for the above approach
import math as Math
 
def findDistinctXOR(n):
 
    # Corner case
    if (n == 1):
        print(1)
    if (n == 2):
        print(2)
    x = None
    next = None
    x = Math.floor(Math.log2(n))
 
    # if n is power of two
    if ((n & (n - 1)) == 0):
        next = Math.pow(2, x + 1)
        print((next - 1))
    else:
        next = Math.pow(2, x + 1)
        print(int(next))
 
# Driver Code
N = 3
findDistinctXOR(N)
 
# This code is contributed by Saurabh Jaiswal

// C# code to implement above approach
using System;
 
class GFG{
 
static void findDistinctXOR(int n)
{
     
    // Corner case
    if (n == 1)
    {
        Console.WriteLine(1);
    }
    if (n == 2)
    {
        Console.WriteLine(2);
    }
 
    long x, next;
    x = (long)Math.Log(n, 2);
 
    // If n is power of two
    if ((n & (n - 1)) == 0)
    {
        next = (long)Math.Pow(2, x + 1);
        Console.WriteLine(next - 1);
    }
    else
    {
        next = (long)Math.Pow(2, x + 1);
        Console.WriteLine(next);
    }
}
 
// Driver Code
public static void Main()
{
    int N = 3;
     
    findDistinctXOR(N);
}
}
 
// This code is contributed by ukasp

<script>
       // JavaScript code for the above approach
       function findDistinctXOR(n)
       {
        
           // Corner case
           if (n == 1) {
               document.write(1 + "<br>")
           }
           if (n == 2) {
               document.write(2 + "<br>")
           }
           let x, next;
           x = Math.floor(Math.log2(n));
            
           // if n is power of two
           if ((n & (n - 1)) == 0) {
               next = Math.pow(2, x + 1);
               document.write((next - 1) + "<br>")
           }
           else {
               next = Math.pow(2, x + 1);
               document.write(next + "<br>")
           }
       }
        
       // Driver Code
       let N = 3;
       findDistinctXOR(N);
        
 // This code is contributed by Potta Lokesh
   </script>

4

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)