Número de pares ordenados tales que (Ai & Aj) = 0

Dada una array A[] de n enteros, encuentre el número de pares ordenados tales que A _i &A _j es cero, donde 0<=(i,j)<n. Considere (i, j) y (j, i) como diferentes.

Restricciones:
1<=n<=10 ⁴
1<=A _i <=10 ⁴

Ejemplos:

Input : A[] = {3, 4, 2}
Output : 4
Explanation : The pairs are (3, 4) and (4, 2) which are 
counted as 2 as (4, 3) and (2, 4) are considered different. 

Input : A[]={5, 4, 1, 6}
Output : 4 
Explanation : (4, 1), (1, 4), (6, 1) and (1, 6) are the pairs

Enfoque simple : un enfoque simple es verificar todos los pares posibles y contar el número de pares ordenados cuyo & bit a bit devuelve 0.

A continuación se muestra la implementación de la idea anterior:

C++

// CPP program to calculate the number
// of ordered pairs such that their bitwise
// and is zero
#include <bits/stdc++.h>
using namespace std;
 
// Naive function to count the number
// of ordered pairs such that their
// bitwise and is 0
int countPairs(int a[], int n)
{
    int count = 0;
 
    // check for all possible pairs
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            if ((a[i] & a[j]) == 0)
 
                // add 2 as (i, j) and (j, i) are
                // considered different
                count += 2;
    }
 
    return count;
}
 
// Driver Code
int main()
{
    int a[] = { 3, 4, 2 };
    int n = sizeof(a) / sizeof(a[0]);   
    cout << countPairs(a, n);   
    return 0;
}

Java

// Java program to calculate the number
// of ordered pairs such that their bitwise
// and is zero
 
class GFG {
     
    // Naive function to count the number
    // of ordered pairs such that their
    // bitwise and is 0
    static int countPairs(int a[], int n)
    {
        int count = 0;
 
        // check for all possible pairs
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++)
                if ((a[i] & a[j]) == 0)
 
                    // add 2 as (i, j) and (j, i) are
                    // considered different
                    count += 2;
        }
 
        return count;
    }
 
    // Driver Code
    public static void main(String arg[])
    {
        int a[] = { 3, 4, 2 };
        int n = a.length;
        System.out.print(countPairs(a, n));
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to calculate the number
# of ordered pairs such that their
# bitwise and is zero
 
# Naive function to count the number
# of ordered pairs such that their
# bitwise and is 0
def countPairs(a, n):
    count = 0
 
    # check for all possible pairs
    for i in range(0, n):
        for j in range(i + 1, n):
            if (a[i] & a[j]) == 0:
 
                # add 2 as (i, j) and (j, i) are
                # considered different
                count += 2
    return count
 
# Driver Code
a = [ 3, 4, 2 ]
n = len(a)
print (countPairs(a, n))
 
# This code is contributed
# by Shreyanshi Arun.

C#

// C# program to calculate the number
// of ordered pairs such that their
// bitwise and is zero
using System;
 
class GFG {
     
    // Naive function to count the number
    // of ordered pairs such that their
    // bitwise and is 0
    static int countPairs(int []a, int n)
    {
        int count = 0;
 
        // check for all possible pairs
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
                if ((a[i] & a[j]) == 0)
 
                    // add 2 as (i, j) and (j, i)
                    // arev considered different
                    count += 2;
        }
 
        return count;
    }
 
    // Driver Code
    public static void Main()
    {
        int []a = { 3, 4, 2 };
        int n = a.Length;
        Console.Write(countPairs(a, n));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to calculate the number
// of ordered pairs such that their
// bitwise and is zero
 
// Naive function to count the number
// of ordered pairs such that their
// bitwise and is 0
function countPairs($a, $n)
{
    $count = 0;
 
    // check for all possible pairs
    for ($i = 0; $i < $n; $i++)
    {
        for ($j = $i + 1; $j < $n; $j++)
            if (($a[$i] & $a[$j]) == 0)
 
                // add 2 as (i, j) and (j, i) are
                // considered different
                $count += 2;
    }
 
    return $count;
}
 
// Driver Code
{
    $a = array(3, 4, 2);
    $n = sizeof($a) / sizeof($a[0]);
    echo countPairs($a, $n);
    return 0;
}
 
// This code is contributed by nitin mittal

JavaScript

<script>
    // JavaScript program to calculate the number
    // of ordered pairs such that their bitwise
    // and is zero
 
    // Naive function to count the number
    // of ordered pairs such that their
    // bitwise and is 0
    const countPairs = (a, n) => {
        let count = 0;
 
        // check for all possible pairs
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++)
                if ((a[i] & a[j]) == 0)
 
                    // add 2 as (i, j) and (j, i) are
                    // considered different
                    count += 2;
        }
 
        return count;
    }
 
    // Driver Code
 
    let a = [3, 4, 2];
    let n = a.length;
    document.write(countPairs(a, n));
 
    // This code is contributed by rakeshsahni
 
</script>
 
 
?>

Producción:

Complejidad temporal: O(n ² )

Enfoque eficiente : un enfoque eficiente es utilizar el método de programación dinámica Sum over Subsets y contar el número de pares ordenados. En el SOS DP encontramos los pares cuyo bit a bit & devolvió 0. Aquí necesitamos contar el número de pares.
Algunas observaciones clave son las restricciones, el máximo que puede tener un elemento de array es 10 ⁴ . Calcular la máscara hasta (1<<15) nos dará nuestra respuesta. Utilice hashing para contar la ocurrencia de cada elemento. Si el último bit está APAGADO, entonces en relación con SOS dp, tendremos un caso base ya que solo hay una posibilidad de bit APAGADO.

dp[mask][0] = freq(mask)

Si el último bit está activado, entonces tendremos el caso base como:

dp[mask][0] = freq(mask) + freq(mask^1)

Agregamos freq(mask^1) para agregar la otra posibilidad de bit OFF.
Iterar sobre N=15 bits, que es el máximo posible.
Consideremos que el i-ésimo bit es 0 , luego ningún subconjunto puede diferir de la máscara en el i-ésimo bit, ya que significaría que los números tendrán un 1 en el i-ésimo bit donde la máscara tiene un 0, lo que significaría que no es un subconjunto de la máscara. Por lo tanto, concluimos que los números ahora difieren solo en los primeros (i-1) bits. Por eso,

DP(mask, i) = DP(mask, i-1)

Ahora el segundo caso, si el i-ésimo bit es 1, se puede dividir en dos conjuntos que no se intersecan. Uno que contiene números con el i-ésimo bit como 1 y que difiere de la máscara en los siguientes (i-1) bits. Segundo que contiene números con i-ésimo bit como 0 y que difiere de la máscara

$\oplus$

(2 ⁱ ) en los siguientes (i-1) bits. Por eso,

DP(mask, i) = DP(mask, i-1) + DP(mask

2^{i, i-1).}

DP[máscara][i] almacena el número de subconjuntos de máscara que difieren de la máscara solo en los primeros i bits. Iterar para todos los elementos de la array, y para cada elemento de la array, agregue el número de subconjuntos (dp[ ( ( 1<<N ) – 1 ) ^ a[i] ][ N ]) al número de pares. N = número máximo de bits.

Explicación de la adición de dp[ ( ( 1<<N ) – 1 ) ^ a[i] ][N] al número de pares: Tome un ejemplo de A[i] siendo 5, que es 101 en binario. Para una mejor comprensión, suponga que N = 3 en este caso, por lo tanto, el reverso de 101 será 010 que al aplicar bit a bit & da 0. Entonces (1<<3) da 1000 que al restarlo de 1 da 111. 111 101 da
$\oplus$
010 que es el bit invertido. Por lo tanto, dp[((1<<N)-1)^a[i]][N] tendrá el número de subconjuntos que devuelve 0 al aplicar el operador bit a bit &.

A continuación se muestra la implementación de la idea anterior:

C++

// CPP program to calculate the number
// of ordered pairs such that their bitwise
// and is zero
 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 15;
 
// efficient function to count pairs
long long countPairs(int a[], int n)
{
    // stores the frequency of each number
    unordered_map<int, int> hash;
 
    long long dp[1 << N][N + 1];
     
    memset(dp, 0, sizeof(dp)); // initialize 0 to all
 
    // count the frequency of every element
    for (int i = 0; i < n; ++i)
        hash[a[i]] += 1;
 
    // iterate for all possible values that a[i] can be
    for (long long mask = 0; mask < (1 << N); ++mask) {
 
        // if the last bit is ON
        if (mask & 1)
            dp[mask][0] = hash[mask] + hash[mask ^ 1];
        else // is the last bit is OFF
            dp[mask][0] = hash[mask];
 
        // iterate till n
        for (int i = 1; i <= N; ++i) {
 
            // if mask's ith bit is set
            if (mask & (1 << i))
            {
                dp[mask][i] = dp[mask][i - 1] +
                        dp[mask ^ (1 << i)][i - 1];
            }   
            else // if mask's ith bit is not set
                dp[mask][i] = dp[mask][i - 1];
        }
    }
 
    long long ans = 0;
 
    // iterate for all the array element
    // and count the number of pairs
    for (int i = 0; i < n; i++)
        ans += dp[((1 << N) - 1) ^ a[i]][N];
 
    // return answer
    return ans;
}
 
// Driver Code
int main()
{
    int a[] = { 5, 4, 1, 6 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << countPairs(a, n);
    return 0;
}

Java

// Java program to calculate
// the number of ordered pairs
// such that their bitwise
// and is zero
import java.util.*;
class GFG{
     
static int N = 15;
   
// Efficient function to count pairs
public static int countPairs(int a[],
                             int n)
{
  // Stores the frequency of
  // each number
  HashMap<Integer,
          Integer> hash = new HashMap<>();
 
  int dp[][] = new int[1 << N][N + 1];
 
  // Initialize 0 to all
   
  // Count the frequency
  // of every element
  for (int i = 0; i < n; ++i)
  {
    if(hash.containsKey(a[i]))
    {
      hash.replace(a[i],
      hash.get(a[i]) + 1);
    }
    else
    {
      hash.put(a[i], 1);
    }
  }
 
  // Iterate for all possible
  // values that a[i] can be
  for (int mask = 0;
           mask < (1 << N); ++mask)
  {
    // If the last bit is ON
    if ((mask & 1) != 0)
    {
      if(hash.containsKey(mask))
      {
        dp[mask][0] = hash.get(mask);
      }
      if(hash.containsKey(mask ^ 1))
      {
        dp[mask][0] += hash.get(mask ^ 1);
      }
    }
    else
    {
      // is the last bit is OFF
      if(hash.containsKey(mask))
      {
        dp[mask][0] = hash.get(mask); 
      }
    }
 
    // Iterate till n
    for (int i = 1; i <= N; ++i)
    {
      // If mask's ith bit is set
      if ((mask & (1 << i)) != 0)
      {
        dp[mask][i] = dp[mask][i - 1] +
                      dp[mask ^ (1 << i)][i - 1];
      }    
      else
      {
        // If mask's ith bit is not set
        dp[mask][i] = dp[mask][i - 1];
      }
    }
  }
 
  int ans = 0;
 
  // Iterate for all the
  // array element and
  // count the number of pairs
  for (int i = 0; i < n; i++)
  {
    ans += dp[((1 << N) - 1) ^ a[i]][N];
  }
 
  // return answer
  return ans;
}
 
// Driver code   
public static void main(String[] args)
{
  int a[] = {5, 4, 1, 6};
  int n = a.length;
  System.out.print(countPairs(a, n));
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python program to calculate the number
# of ordered pairs such that their bitwise
# and is zero
N = 15
 
# efficient function to count pairs
def countPairs(a, n):
 
    # stores the frequency of each number
    Hash = {}
     
    # initialize 0 to all
    dp = [[0 for i in range(N + 1)] for j in range(1 << N)]
 
    # count the frequency of every element
    for i in range(n):
        if a[i] not in Hash:
            Hash[a[i]] = 1
        else:
            Hash[a[i]] += 1
 
    # iterate for all possible values that a[i] can be
    mask = 0
    while(mask < (1 << N)):
        if mask not in Hash:
            Hash[mask] = 0
 
        # if the last bit is ON
        if(mask & 1):
            dp[mask][0] = Hash[mask] + Hash[mask ^ 1]
             
        else:    # is the last bit is OFF
            dp[mask][0] = Hash[mask]
 
        # iterate till n
        for i in range(1, N + 1):
 
            # if mask's ith bit is set
            if(mask & (1 << i)):
                dp[mask][i] = dp[mask][i - 1] + dp[mask ^ (1 << i)][i - 1]
                 
            else:    # if mask's ith bit is not set
                dp[mask][i] = dp[mask][i - 1]
 
        mask += 1
 
    ans = 0
     
    # iterate for all the array element
    # and count the number of pairs
    for i in range(n):
        ans += dp[((1 << N) - 1) ^ a[i]][N]
         
    # return answer
    return ans
 
# Driver Code
a = [5, 4, 1, 6]
n = len(a)
print(countPairs(a, n))
 
# This code is contributed by avanitrachhadiya2155

C#

// C# program to calculate
// the number of ordered pairs
// such that their bitwise
// and is zero
using System;
using System.Collections.Generic;
 
class GFG {
     
    static int N = 15;
    
    // Efficient function to count pairs
    static int countPairs(int[] a, int n)
    {
      // Stores the frequency of
      // each number
      Dictionary<int, int> hash = new Dictionary<int, int>();
      
      int[, ] dp = new int[1 << N, N + 1];
      
      // Initialize 0 to all
        
      // Count the frequency
      // of every element
      for (int i = 0; i < n; ++i)
      {
        if(hash.ContainsKey(a[i]))
        {
          hash[a[i]] += 1;
        }
        else
        {
          hash.Add(a[i], 1);
        }
      }
      
      // Iterate for all possible
      // values that a[i] can be
      for (int mask = 0;
               mask < (1 << N); ++mask)
      {
        // If the last bit is ON
        if ((mask & 1) != 0)
        {
          if(hash.ContainsKey(mask))
          {
            dp[mask, 0] = hash[mask];
          }
          if(hash.ContainsKey(mask ^ 1))
          {
            dp[mask, 0] += hash[mask ^ 1];
          }
        }
        else
        {
          // is the last bit is OFF
          if(hash.ContainsKey(mask))
          {
            dp[mask, 0] = hash[mask]; 
          }
        }
      
        // Iterate till n
        for (int i = 1; i <= N; ++i)
        {
           
          // If mask's ith bit is set
          if ((mask & (1 << i)) != 0)
          {
            dp[mask, i] = dp[mask, i - 1] +
                          dp[mask ^ (1 << i), i - 1];
          }    
          else
          {
             
            // If mask's ith bit is not set
            dp[mask, i] = dp[mask, i - 1];
          }
        }
      }
      
      int ans = 0;
      
      // Iterate for all the
      // array element and
      // count the number of pairs
      for (int i = 0; i < n; i++)
      {
        ans += dp[((1 << N) - 1) ^ a[i], N];
      }
      
      // return answer
      return ans;
    }
    
  // Driver code
  static void Main()
  {
      int[] a = {5, 4, 1, 6};
      int n = a.Length;
      Console.WriteLine(countPairs(a, n));
  }
}
 
// This code is contributed by divyesh072019

Producción:

Complejidad Temporal: O(N*2 ^N ) donde N=15 que es el máximo número de bits posible, ya que A _max =10 ⁴ .

Publicación traducida automáticamente

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

C++

Java

Python3

C#

PHP

JavaScript

C++

Java

Python3

C#

Deja una respuesta Cancelar la respuesta