Recuento de enteros K en el rango [0, N] tales que (K XOR K+1) es igual a (K+2 XOR K+3)

Dado un número entero N , la tarea es imprimir el recuento de todos los números enteros no negativos K menores o iguales a N, de modo que el XOR bit a bit de K y K+1 sea igual al XOR bit a bit de K+2 y K+3 .

Ejemplos:

Entrada: N = 3
Salida: 2
Explicación: 
Los números que cumplen las condiciones son:

1. K = 0, el XOR bit a bit de 0 y 1 es igual a 1 y el xor bit a bit de 2 y 3 también es igual a 1.
2. K = 2, el XOR bit a bit de 2 y 3 es igual a 1 y el xor bit a bit de 4 y 5 también es igual a 1.

Por lo tanto, hay 2 números que cumplen la condición.

Entrada: 4
Salida: 3

Enfoque ingenuo: el enfoque más simple es iterar sobre el rango [0, N] y verificar si el número actual cumple la condición o no. Si satisface, incremente el conteo en 1 . Después de verificar todos los números, imprima el valor del conteo.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior puede optimizarse mediante la observación de que todos los números pares en el rango [0, N] satisfacen la condición dada.

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 all the integers
// less than N satisfying the given
// condition
int countXor(int N)
{
 
    // Store the count of even
    // numbers less than N+1
    int cnt = N / 2 + 1;
 
    // Return the count
    return cnt;
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 4;
 
    // Function Call
    cout << countXor(N);
 
    return 0;
}

// Java Program for the above approach
import java.io.*;
 
class GFG
{
   
    // Function to count all the integers
    // less than N satisfying the given
    // condition
    static int countXor(int N)
    {
 
        // Store the count of even
        // numbers less than N+1
        int cnt = (int) N / 2 + 1;
 
        // Return the count
        return cnt;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given Input
        int N = 4;
 
        // Function Call
        System.out.println(countXor(N));
 
    }
}
 
// This code is contributed by Potta Lokesh

# Python 3 program for the above approach
 
# Function to count all the integers
# less than N satisfying the given
# condition
def countXor(N):
   
    # Store the count of even
    # numbers less than N+1
    cnt = N // 2 + 1
 
    # Return the count
    return cnt
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    N = 4
 
    # Function Call
    print(countXor(N))
     
    # This code is contributed by SUTENDRA_GANGWAR.

// C# program for the above approach
using System;
 
class GFG{
     
// Function to count all the integers
// less than N satisfying the given
// condition
static int countXor(int N)
{
     
    // Store the count of even
    // numbers less than N+1
    int cnt = (int)N / 2 + 1;
 
    // Return the count
    return cnt;
}
 
// Driver code
static void Main()
{
     
    // Given Input
    int N = 4;
 
    // Function Call
    Console.WriteLine(countXor(N));
}
}
 
// This code is contributed by abhinavjain194

<script>
  
        // JavaScript program for the above approach
 
 
        // Function to count all the integers
        // less than N satisfying the given
        // condition
        function countXor(N) {
 
            // Store the count of even
            // numbers less than N+1
            let cnt = Math.floor(N / 2) + 1;
 
            // Return the count
            return cnt;
        }
 
        // Driver Code
 
        // Given Input
        let N = 4;
 
        // Function Call
        document.write(countXor(N));
 
    // This code is contributed by Potta Lokesh
 
</script>

3

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