Recuento de x en un rango dado tal que bit a bit XOR de x, (x+1) y (x+2), (x+3) son iguales

Dado un número entero N , la tarea es contar el número de números enteros (digamos x ) en el rango [0, 2 ^N −1] tal que x⊕(x+1) = (x+2)⊕(x+3) . [donde ⊕ representa bit a bit Xor]

Ejemplos :

Entrada : N = 1
Salida : 1
Explicación : Solo 0 es la x válida, ya que, 0 ⊕ 1 = 2 ⊕ 3 = 1

Entrada : N = 3
Salida : 4

Enfoque ingenuo : el enfoque simple para resolver el problema dado es generar todos los valores posibles de x en el rango [0, 2 ^N −1] y verificar si satisfacen los criterios dados, es decir, x⊕(x+1) = (x+ 2)⊕(x+3) . 

Siga los pasos mencionados a continuación para implementar la idea:

• Iterar de i = 0 a N .
  • Comprobar si (i ⊕ (i+1)) = ((i+2) ⊕ (i+3))
  • Si se cumple la condición, incremente la cuenta de dichos números.
• Devuelve el conteo final como la respuesta.

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

// C++ code to implement the approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find number of integers
// satisfying the condition
int countOfvalues(int N)
{
    // Stores the resultant count of pairs
    int count = 0;
 
    for (int i = 0; i < (1 << N); i++) {
 
        // Iterate over the range
        if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3)))
            count += 1;
    }
    return count;
}
// Driver Code
int main()
{
    int N = 3;
 
    // Function call
    cout << countOfvalues(N);
    return 0;
}
 
// This code is contributed by Rohit Pradhan

// Java code to implement the approach
class GFG {
 
  // Function to find number of integers
  // satisfying the condition
  public static int countOfvalues(int N)
  {
 
    // Stores the resultant count of pairs
    int count = 0;
 
    for (int i = 0; i < (1 << N); i++) {
 
      // Iterate over the range
      if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3)))
        count += 1;
    }
    return count;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 3;
 
    // Function call
    System.out.println(countOfvalues(N));
  }
}
 
// This code is contributed by phasing17

# Python3 code to implement the approach
 
# Function to find number of integers
# satisfying the condition
def countOfvalues(N):
         
    # Stores the resultant count of pairs
    count = 0
 
    for i in range(0, 2**N):
 
       # Iterate over the range
        if i ^ (i + 1) == (i + 2) ^ (i + 3):
            count += 1
 
    return count
 
 
# Driver Code
if __name__ == '__main__':
    N = 3
     
    # Function call
    print(countOfvalues(N))

// C# Program of the above approach
using System;
 
class GFG
{
 
  // Function to find number of integers
  // satisfying the condition
  public static int countOfvalues(int N)
  {
 
    // Stores the resultant count of pairs
    int count = 0;
 
    for (int i = 0; i < (1 << N); i++) {
 
      // Iterate over the range
      if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3)))
        count += 1;
    }
    return count;
  }
 
  // Driver Code
  public static void Main ()
  {
    int N = 3;
 
    // Function call
    Console.Write(countOfvalues(N));
  }
}
 
// This code is contributed by sanjoy_62.

<script>
       // JavaScript code for the above approach
 
       // Function to find number of integers
       // satisfying the condition
       function countOfvalues(N)
       {
        
           // Stores the resultant count of pairs
           let count = 0;
 
           for (let i = 0; i < (1 << N); i++) {
 
               // Iterate over the range
               if ((i ^ (i + 1)) == ((i + 2) ^ (i + 3)))
                   count += 1;
           }
           return count;
       }
        
       // Driver Code
       let N = 3;
 
       // Function call
       document.write(countOfvalues(N));
 
   // This code is contributed by Potta Lokesh
   </script>

4

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

Enfoque eficiente: el problema se puede resolver de manera eficiente con base en la siguiente idea matemática:

• Si x es tal que es un número par, entonces x+2 también es un número par y tanto (x+1) como (x+3) serán números impares. 
• Ahora, dos números pares e impares consecutivos tienen solo una diferencia de un bit solo en su posición LSB.
• Entonces, el XOR bit a bit de ( x y x+1 ) y ( x+2 y x+3 ) ambos serán 1 , cuando x es par.
• Por lo tanto, todos los números pares en el rango dado [0, 2 ^N −1] es un valor posible de x.

Entonces, el número total de tales valores es (2 ^N – 1)/2 = 2 ^N-1

Siga la ilustración a continuación para visualizar mejor la idea:

Ilustración:

Considere N = 3 . Entonces los números están en el rango [0, 7]

Todos los números pares en el rango son 0, 2, 4 y 6

=> Cuando x = 0: 0 ⊕ 1 = 1 y 2 ⊕ 3 = 1. Por lo tanto, la relación se cumple
=> Cuando x = 2: 2 ⊕ 3 = 1 y 4 ⊕ 5 = 1. Por lo tanto, la relación se cumple
=> Cuando x = 4. 4 ⊕ 5 = 1 y 6 ⊕ 7 = 1. Por lo tanto, la relación se cumple
=> Cuando x = 6: 6 ⊕ 7 = 1 y 8 ⊕ 9 = 1. Por lo tanto, la relación se cumple.

Ahora para los números impares si se hace:

=> Cuando x = 1: 1 ⊕ 2 = 3 y 3 ⊕ 4 = 7. Por lo tanto, la relación no se cumple.
=> Cuando x = 3: 3 ⊕ 4 = 7 y 5 ⊕ 6 = 3. Por lo tanto, la relación no se cumple.
=> Cuando x = 5: 5 ⊕ 6 = 3 y 7 ⊕ 8 = 15. Por lo tanto, la relación no se cumple.
=> Cuando x = 7: 7 ⊕ 8 = 15 y 9 ⊕ 10 = 3. Por lo tanto, la relación no se cumple.

Así que los valores totales posibles son 4 = 2 ^3-1

Por lo tanto, para obtener la respuesta, calcule el valor de 2 ^N-1 para N dado

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// the number of possible values
int countValues(int N) { return pow(2, N - 1); }
 
// Driver Code
int main()
{
    int N = 3;
    // Function call
    cout << countValues(N);
    return 0;
}
 
// This code is contributed by Rohit Pradhan

// Java code to implement the above approach
class GFG {
 
  // Function to calculate
  // the number of possible values
  public static int countValues(int N) { return (int)Math.pow(2, N - 1); }
 
  public static void main(String[] args) {
    int N = 3;
 
    // Function call
    System.out.println(countValues(N));
  }
}
 
//This code is contributed by phasing17

# Python code to implement the above approach
 
# Function to calculate
# the number of possible values
def countOfValues (N):
    return pow(2, N - 1)
 
# Driver code
if __name__ == '__main__':
    N = 3
     
    # Function call
    res = countOfValues(N)
    print(res)

// C# program for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to calculate
  // the number of possible values
  public static int countValues(int N)
  {
    return (int)Math.Pow(2, N - 1);
 
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int N = 3;
 
    // Function call
    Console.Write(countValues(N));
  }
}
 
// This code is contributed by code_hunt.

<script>
 
// JavaScript code to implement the above approach
 
// Function to calculate
// the number of possible values
function countValues(N)
{
    return Math.pow(2, N - 1);
}
 
// Driver Code
let N = 3;
 
// Function call
document.write(countValues(N));
 
// This code is contributed by shinjanpatra
 
</script>

4

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