Contar pares de un rango dado que tengan valores Bitwise OR y XOR iguales

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es encontrar el número total de pares (P, Q) del rango 0 ≤ P, Q < 2 N , tal que P OR Q = P XOR Q . Dado que el conteo puede ser muy grande, imprímalo en módulo 10 9 + 7 .

Ejemplos:

Entrada: N = 1
Salida: 3
Explicación: Los pares (P, Q) que satisfacen P OR Q = P XOR Q son (0, 0), (0, 1) y (1, 0). Por lo tanto, la salida 3.

Entrada: N = 3
Salida: 27

 

Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles (P, Q) y contar los pares que satisfacen P OR Q = P XOR Q.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
 
// Function to calculate
// (x^y)%MOD
long long int power(int x, int y)
{
 
    // Initialize result
    long long int res = 1;
 
    // Update x if it is more than or
    // equal to MOD
    x = x % MOD;
 
    while (y > 0) {
 
        // If y is odd, multiply
        // x with result
        if (y & 1)
            res = (res * x) % MOD;
 
        // y must be even now
        // y = y/2
        y = y >> 1;
        x = (x * x) % MOD;
    }
 
    // Return (x^y)%MOD
    return res;
}
 
// Function to count total pairs
void countPairs(int N)
{
    // The upper bound is 2^N
    long long int high = power(2, N);
 
    // Stores the count of pairs
    int count = 0;
 
    // Generate all possible pairs
    for (int i = 0; i < high; i++) {
        for (int j = 0; j < high; j++) {
 
            // Find XOR of both integers
            int X = (i ^ j);
 
            // Find OR of both integers
            int Y = (i | j);
 
            // If both are equal
            if (X == Y) {
 
                // Increment count
                count++;
            }
        }
    }
 
    // Print count%MOD
    cout << count % MOD << endl;
}
 
// Driver Code
int main()
{
    int N = 10;
 
    // Function Call
    countPairs(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
class GFG
{
 
static int MOD = 1000000007;
   
// Function to calculate
// (x^y)%MOD
static int power(int x, int y)
{
 
    // Initialize result
    int res = 1;
 
    // Update x if it is more than or
    // equal to MOD
    x = x % MOD;
    while (y > 0)
    {
 
        // If y is odd, multiply
        // x with result
        if ((y & 1) != 0)
            res = (res * x) % MOD;
 
        // y must be even now
        // y = y/2
        y = y >> 1;
        x = (x * x) % MOD;
    }
 
    // Return (x^y)%MOD
    return res;
}
 
// Function to count total pairs
static void countPairs(int N)
{
   
    // The upper bound is 2^N
    int high = power(2, N);
 
    // Stores the count of pairs
    int count = 0;
 
    // Generate all possible pairs
    for (int i = 0; i < high; i++)
    {
        for (int j = 0; j < high; j++)
        {
 
            // Find XOR of both integers
            int X = (i ^ j);
 
            // Find OR of both integers
            int Y = (i | j);
 
            // If both are equal
            if (X == Y)
            {
 
                // Increment count
                count++;
            }
        }
    }
 
    // Print count%MOD
    System.out.println(count % MOD);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 10;
 
    // Function Call
    countPairs(N);
}
}
 
// This code is contributed by susmitakundugoaldanga.

Python3

# Python program for the above approach
 
# Function to calculate
# (x^y)%MOD
def power(x, y):
    MOD = 1000000007
     
    # Initialize result
    res = 1
     
    # Update x if it is more than or
    # equal to MOD
    x = x % MOD
    while (y > 0):
       
        # If y is odd, multiply
        # x with result
        if (y & 1):
            res = (res * x) % MOD
             
        # y must be even now
        #  y = y/2
        y = y >> 1
        x = (x * x) % MOD
 
    # Return (x^y)%MOD
    return res
 
# Function to count total pairs
def countPairs( N):
    MOD = 1000000007
     
    # The upper bound is 2^N
    high = power(2, N)
 
    # Stores the count of pairs
    count = 0
 
    # Generate all possible pairs
    for i in range(high):
        for j in range(high):
 
            # Find XOR of both integers
            X = (i ^ j)
 
            # Find OR of both integers
            Y = (i | j)
 
            # If both are equal
            if (X == Y):
 
                # Increment count
                count += 1
 
    # Print count%MOD
    print(count % MOD)
 
# Driver Code
N = 10
 
# Function Call
countPairs(N)
 
# This code is contributed by rohitsingh07052.

C#

// C# program for the above approach
using System;
 
class GFG{
 
  static int MOD = 1000000007;
 
  // Function to calculate
  // (x^y)%MOD
  static int power(int x, int y)
  {
 
    // Initialize result
    int res = 1;
 
    // Update x if it is more than or
    // equal to MOD
    x = x % MOD;
    while (y > 0)
    {
 
      // If y is odd, multiply
      // x with result
      if ((y & 1) != 0)
        res = (res * x) % MOD;
 
      // y must be even now
      // y = y/2
      y = y >> 1;
      x = (x * x) % MOD;
    }
 
    // Return (x^y)%MOD
    return res;
  }
 
  // Function to count total pairs
  static void countPairs(int N)
  {
 
    // The upper bound is 2^N
    int high = power(2, N);
 
    // Stores the count of pairs
    int count = 0;
 
    // Generate all possible pairs
    for (int i = 0; i < high; i++)
    {
      for (int j = 0; j < high; j++)
      {
 
        // Find XOR of both integers
        int X = (i ^ j);
 
        // Find OR of both integers
        int Y = (i | j);
 
        // If both are equal
        if (X == Y)
        {
 
          // Increment count
          count++;
        }
      }
    }
 
    // Print count%MOD
    Console.WriteLine(count % MOD);
  }
 
 
  // Driver Code
  static public void Main()
  {
    int N = 10;
 
    // Function Call
    countPairs(N);
  }
}
 
// This code is contributed by susmitakundugoaldanga.

Javascript

<script>
 
// Javascript program for the above approach
 
     MOD = 1000000007;
 
    // Function to calculate
    // (x^y)%MOD
    function power(x , y) {
 
        // Initialize result
        var res = 1;
 
        // Update x if it is more than or
        // equal to MOD
        x = x % MOD;
        while (y > 0) {
 
            // If y is odd, multiply
            // x with result
            if ((y & 1) != 0)
                res = (res * x) % MOD;
 
            // y must be even now
            // y = y/2
            y = y >> 1;
            x = (x * x) % MOD;
        }
 
        // Return (x^y)%MOD
        return res;
    }
 
    // Function to count total pairs
    function countPairs(N) {
 
        // The upper bound is 2^N
        var high = power(2, N);
 
        // Stores the count of pairs
        var count = 0;
 
        // Generate all possible pairs
        for (i = 0; i < high; i++) {
            for (j = 0; j < high; j++) {
 
                // Find XOR of both integers
                var X = (i ^ j);
 
                // Find OR of both integers
                var Y = (i | j);
 
                // If both are equal
                if (X == Y) {
 
                    // Increment count
                    count++;
                }
            }
        }
 
        // Print count%MOD
        document.write(count % MOD);
    }
 
    // Driver Code
     
        var N = 10;
 
        // Function Call
        countPairs(N);
 
// This code contributed by Rajput-Ji
 
</script>
Producción: 

59049

 

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

Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:

  • Considere el par como (P, Q) . Fije P y luego encuentre todas las Q que satisfagan esta ecuación. Por lo tanto, todos los bits que se establecen en P se desactivarán en Q.
  • Para cada bit no establecido en P , hay dos opciones, es decir, los bits correspondientes en Q pueden ser 0 o 1 .
  • Entonces, para cualquier P, si el número de bits no establecidos en P es u(P), entonces el número de Q será ans1 = 2^u(P) .
  • Iterar sobre el rango [0, N] usando la variable i , luego para cada 2 i tendré una contribución de N C i . Sea esta cuenta ans2 .
  • Entonces, el conteo de pares viene dado por ∑(ans1*ans2) = (1 + 2) N = 3 N .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
 
// Function to find the value of (x^y)%MOD
long long int power(int x, int y)
{
    // Initialize result
    long long int res = 1;
 
    // Update x if it is more than or
    // equal to MOD
    x = x % MOD;
 
    while (y > 0) {
 
        // If y is odd, multiply
        // x with result
        if (y & 1)
            res = (res * x) % MOD;
 
        // y must be even now, then
        // update y/2
        y = y >> 1;
        x = (x * x) % MOD;
    }
 
    // Return (x^y)%MOD
    return res;
}
 
// Function to count total pairs
void countPairs(int N)
{
    // Finding 3^N % 10^9+7
    cout << power(3, N);
}
 
// Driver Code
int main()
{
    int N = 10;
 
    // Function Call
    countPairs(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
  static final int MOD = 1000000007;
 
  // Function to find the value of (x^y)%MOD
  static int power(int x, int y)
  {
 
    // Initialize result
    int res = 1;
 
    // Update x if it is more than or
    // equal to MOD
    x = x % MOD;
    while (y > 0)
    {
 
      // If y is odd, multiply
      // x with result
      if (y % 2== 1)
        res = (res * x) % MOD;
 
      // y must be even now, then
      // update y/2
      y = y >> 1;
      x = (x * x) % MOD;
    }
 
    // Return (x^y)%MOD
    return res;
  }
 
  // Function to count total pairs
  static void countPairs(int N)
  {
 
    // Finding 3^N % 10^9+7
    System.out.print(power(3, N));
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 10;
 
    // Function Call
    countPairs(N);
  }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python program for the above approach
MOD = 1000000007;
 
# Function to find the value of (x^y)%MOD
def power(x, y):
   
    # Initialize result
    res = 1;
 
    # Update x if it is more than or
    # equal to MOD
    x = x % MOD;
    while (y > 0):
 
        # If y is odd, multiply
        # x with result
        if (y % 2 == 1):
            res = (res * x) % MOD;
 
        # y must be even now, then
        # update y/2
        y = y >> 1;
        x = (x * x) % MOD;
 
    # Return (x^y)%MOD
    return res;
 
# Function to count total pairs
def countPairs(N):
   
    # Finding 3^N % 10^9+7
    print(power(3, N));
 
# Driver Code
if __name__ == '__main__':
    N = 10;
 
    # Function Call
    countPairs(N);
 
# This code is contributed by 29AjayKumar

C#

// C# program for the above approach
using System;
public class GFG
{
  static readonly int MOD = 1000000007;
 
  // Function to find the value of (x^y)%MOD
  static int power(int x, int y)
  {
 
    // Initialize result
    int res = 1;
 
    // Update x if it is more than or
    // equal to MOD
    x = x % MOD;
    while (y > 0)
    {
 
      // If y is odd, multiply
      // x with result
      if (y % 2== 1)
        res = (res * x) % MOD;
 
      // y must be even now, then
      // update y/2
      y = y >> 1;
      x = (x * x) % MOD;
    }
 
    // Return (x^y)%MOD
    return res;
  }
 
  // Function to count total pairs
  static void countPairs(int N)
  {
 
    // Finding 3^N % 10^9+7
    Console.Write(power(3, N));
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int N = 10;
 
    // Function Call
    countPairs(N);
  }
}
 
// This code contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program for the above approach
     var MOD = 1000000007;
 
    // Function to find the value of (x^y)%MOD
    function power(x , y) {
 
        // Initialize result
        var res = 1;
 
        // Update x if it is more than or
        // equal to MOD
        x = x % MOD;
        while (y > 0) {
 
            // If y is odd, multiply
            // x with result
            if (y % 2 == 1)
                res = (res * x) % MOD;
 
            // y must be even now, then
            // update y/2
            y = y >> 1;
            x = (x * x) % MOD;
        }
 
        // Return (x^y)%MOD
        return res;
    }
 
    // Function to count total pairs
    function countPairs(N) {
 
        // Finding 3^N % 10^9+7
        document.write(power(3, N));
    }
 
    // Driver Code
     
        var N = 10;
 
        // Function Call
        countPairs(N);
 
// This code contributed by Rajput-Ji
 
</script>
Producción: 

59049

 

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

Publicación traducida automáticamente

Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *