Contar formas de representar N como XOR de enteros distintos que no excedan N

Dado un entero positivo N , la tarea es encontrar el número de formas de representar N como Bitwise XOR de distintos enteros positivos menores o iguales que N .

Ejemplos:

Entrada: N = 5
Salida: 4
Explicación: El número dado N(= 5) se puede representar como:

1. 5 = 5
2. 5 = (4 ^ 1)
3. 5 = (5 ^ 3 ^ 2 ^ 1)
4. 5 = (4 ^ 3 ^ 2)

Por lo tanto, la cuenta total es 4.

Entrada: N = 6
Salida: 8

Enfoque ingenuo: el enfoque más simple para resolver el problema es encontrar todos los subconjuntos de los primeros N números naturales y contar esos subconjuntos que tienen el valor N Bitwise XOR . Después de verificar todos los subconjuntos, imprima el valor total del conteo obtenido. 

Complejidad de Tiempo: O(N * 2 ^N )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la observación de que el número de formas de representar N como el XOR bit a bit de enteros positivos distintos está dado por  .

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

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to count number of ways
// to represent N as the Bitwise
// XOR of distinct integers
void countXorPartition(int N)
{
     
    // Count number of subsets using
    // above-mentioned formula
    double a = pow(2, floor(N - log(N + 1) /
                                log(2)));
     
    // Print the resultant count
    cout << a;
}
   
// Driver Code
int main()
{
    int N = 5;
     
    countXorPartition(N);
}
 
// This code is contributed by SURENDRA_GANGWAR

// java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to count number of ways
// to represent N as the Bitwise
// XOR of distinct integers
static void countXorPartition(int N)
{
     
    // Count number of subsets using
    // above-mentioned formula
    double a = Math.pow(2, (int)(N - Math.log(N + 1) /
                                Math.log(2)));
     
    // Print the resultant count
    System.out.print(a);
}
   
// Driver Code
public static void main(String[] args)
{
    int N = 5;  
    countXorPartition(N);
}
}
 
// This code is contributed by shivanisinghss2110

# Python program for the above approach
 
from math import * 
 
# Function to count number of ways
# to represent N as the Bitwise
# XOR of distinct integers
def countXorPartition(N):
   
  # Count number of subsets using
  # above-mentioned formula
  a = 2**floor(N - log(N + 1)/log(2))
   
  # Print the resultant count
  print(int(a))
 
# Driver Code
 
N = 5
countXorPartition(N)

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count number of ways
// to represent N as the Bitwise
// XOR of distinct integers
static void countXorPartition(int N)
{
     
    // Count number of subsets using
    // above-mentioned formula
    double a = Math.Pow(2, (int)(N - Math.Log(N + 1) /
                                Math.Log(2)));
     
    // Print the resultant count
    Console.Write(a);
}
   
// Driver Code
public static void Main()
{
    int N = 5;  
    countXorPartition(N);
}
}
 
// This code is contributed by ipg2016107.

<script>
 
// JavaScript program for the above approach
 
// Function to count number of ways
// to represent N as the Bitwise
// XOR of distinct integers
function countXorPartition(N)
{
     
    // Count number of subsets using
    // above-mentioned formula
    let a = Math.pow(2, Math.floor(N - Math.log(N + 1) /
                                Math.log(2)));
     
    // Print the resultant count
    document.write(a);
}
   
// Driver Code
    let N = 5;
     
    countXorPartition(N);
 
</script>

4

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