Contar pares de una array cuyo Bitwise OR es mayor que Bitwise AND

Dada una array A[] que consta de N enteros, la tarea es contar el número de pares (i, j) tales que i < j , y Bitwise OR de A[i] y A[j] es mayor que Bitwise AND de A[i] y A[j] .

Ejemplos:

Entrada: A[] = {1, 4, 7}
Salida: 3
Explicación: 
Hay 3 pares de este tipo: (1, 4), (4, 7), (1, 7).
1) 1 | 4 (= 5) > 1 y 4 (= 0)
2) 4 | 7 (= 7) > 4 y 7 (= 4)
3) 1 | 7 (= 7) > 1 y 7 (= 1)

Entrada: A[] = {3, 3, 3}
Salida: 0
Explicación: No existe tal par.

Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles a partir de la array dada y para cada par (i, j) , si cumple con las condiciones dadas, luego incremente el conteo en 1 . Después de verificar todos los pares, imprima el valor de count como resultado.

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 the number of
// pairs (i, j) their Bitwise OR is
// greater than Bitwise AND
void countPairs(int A[], int n)
{
    // Store the required answer
    int count = 0;
 
    // Check for all possible pairs
    for (int i = 0; i < n; i++) {
 
        for (int j = i + 1; j < n; j++)
 
            // If the condition satisfy
            // then increment count by 1
            if ((A[i] | A[j])
                > (A[i] & A[j])) {
                count++;
            }
    }
 
    // Print the answer
    cout << count;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 4, 7 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    countPairs(A, N);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
  // Function to count the number of
  // pairs (i, j) their Bitwise OR is
  // greater than Bitwise AND
  static void countPairs(int A[], int n)
  {
    // Store the required answer
    int count = 0;
 
    // Check for all possible pairs
    for (int i = 0; i < n; i++) {
 
      for (int j = i + 1; j < n; j++)
 
        // If the condition satisfy
        // then increment count by 1
        if ((A[i] | A[j])
            > (A[i] & A[j])) {
          count++;
        }
    }
 
    // Print the answer
    System.out.println(count);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int A[] = { 1, 4, 7 };
    int N = A.length;
 
    // Function Call
    countPairs(A, N);
  }
}
 
// This code is contributed by splevel62.

# Python program to implement
# the above approach
 
# Function to count the number of
# pairs (i, j) their Bitwise OR is
# greater than Bitwise AND
def countPairs(A, n):
   
    # Store the required answer
    count = 0;
 
    # Check for all possible pairs
    for i in range(n):
        for j in range(i + 1, n):
 
            # If the condition satisfy
            # then increment count by 1
            if ((A[i] | A[j]) > (A[i] & A[j])):
                count += 1;
 
    # Print the answer
    print(count);
 
# Driver Code
if __name__ == '__main__':
    A = [1, 4, 7];
    N = len(A);
 
    # Function Call
    countPairs(A, N);
 
    # This code is contributed by 29AjayKumar

// C# program to implement
// the above approach
using System;
class GFG
{
  // Function to count the number of
  // pairs (i, j) their Bitwise OR is
  // greater than Bitwise AND
  static void countPairs(int[] A, int n)
  {
    // Store the required answer
    int count = 0;
 
    // Check for all possible pairs
    for (int i = 0; i < n; i++) {
 
      for (int j = i + 1; j < n; j++)
 
        // If the condition satisfy
        // then increment count by 1
        if ((A[i] | A[j])
            > (A[i] & A[j])) {
          count++;
        }
    }
 
    // Print the answer
    Console.Write(count);
}
 
// Driver Code
public static void Main()
{
    int[] A = { 1, 4, 7 };
    int N = A.Length;
 
    // Function Call
    countPairs(A, N);
}
}
 
// This code is contributed by susmitakundugoaldanga.

<script>
 
 
// Javascript program for the above approach
 
// Function to count the number of
// pairs (i, j) their Bitwise OR is
// greater than Bitwise AND
function countPairs( A, n)
{
    // Store the required answer
    var count = 0;
 
    // Check for all possible pairs
    for (var i = 0; i < n; i++) {
 
        for (var j = i + 1; j < n; j++)
 
            // If the condition satisfy
            // then increment count by 1
            if ((A[i] | A[j])
                > (A[i] & A[j])) {
                count++;
            }
    }
 
    // Print the answer
    document.write( count);
}
 
// Driver Code
var A = [ 1, 4, 7 ];
var N = A.length;
// Function Call
countPairs(A, N);
 
</script>

3

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

Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en la observación de que la condición Ai | Aj > Ai & Aj se satisface solo cuando Ai y Aj son distintos. Si Ai es igual a Aj , entonces Ai | Aj = Ai y Aj . La condición Ai | Aj < Ai & Aj nunca se cumple. Por lo tanto, el problema se puede resolver restando el número de pares que tienen el mismo valor del número total de pares posibles. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos count , con N * (N – 1) / 2 que indica el número total de pares posibles.
• Inicialice un hashmap , diga M para almacenar la frecuencia de cada elemento de la array .
• Recorra la array arr[] y para cada elemento de la array arr[i] , incremente la frecuencia de arr[i] en M en 1 .
• Ahora, recorra el hashmap M y para cada clave K , y su valor correspondiente X , reste el valor de (X * (X – 1))/2 de la cuenta .
• Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

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 the number of
// pairs (i, j) their Bitwise OR is
// greater than Bitwise AND
void countPairs(int A[], int n)
{
    // Total number of pairs
    // possible from the array
    long long count = (n * (n - 1)) / 2;
 
    // Stores frequency of each array element
    unordered_map<long long, long long> ump;
 
    // Traverse the array A[]
    for (int i = 0; i < n; i++) {
 
        // Increment ump[A[i]] by 1
        ump[A[i]]++;
    }
 
    // Traverse the Hashmap ump
    for (auto it = ump.begin();
         it != ump.end(); ++it) {
 
        // Subtract those pairs (i, j)
        // from count which has the
        // same element on index i
        // and j (i < j)
        long long c = it->second;
        count = count - (c * (c - 1)) / 2;
    }
 
    // Print the result
    cout << count;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 4, 7 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    countPairs(A, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to count the number of
// pairs (i, j) their Bitwise OR is
// greater than Bitwise AND
static void countPairs(int A[], int n)
{
    // Total number of pairs
    // possible from the array
    int count = (n * (n - 1)) / 2;
 
    // Stores frequency of each array element
    Map<Integer,Integer> mp = new HashMap<>();
 
    // Traverse the array A[]
    for (int i = 0 ; i < n; i++){
        if(mp.containsKey(A[i])){
            mp.put(A[i], mp.get(A[i])+1);
        }
        else{
            mp.put(A[i], 1);
        }
    }
 
    // Traverse the Hashmap ump
    for (Map.Entry<Integer,Integer> it : mp.entrySet()){
 
        // Subtract those pairs (i, j)
        // from count which has the
        // same element on index i
        // and j (i < j)
        int c = it.getValue();
        count = count - (c * (c - 1)) / 2;
    }
 
    // Print the result
    System.out.print(count);
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 1, 4, 7 };
    int N = A.length;
 
    // Function Call
    countPairs(A, N);
}
}
 
// This code is contributed by shikhasingrajput

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to count the number of
# pairs (i, j) their Bitwise OR is
# greater than Bitwise AND
def countPairs(A, n):
 
    # Total number of pairs
    # possible from the array
    count = (n * (n - 1)) // 2
 
    # Stores frequency of each array element
    ump = defaultdict(int)
 
    # Traverse the array A[]
    for i in range(n):
 
        # Increment ump[A[i]] by 1
        ump[A[i]] += 1
 
    # Traverse the Hashmap ump
    for it in ump.keys():
 
        # Subtract those pairs (i, j)
        # from count which has the
        # same element on index i
        # and j (i < j)
        c = ump[it]
        count = count - (c * (c - 1)) // 2
 
    # Print the result
    print(count)
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 4, 7]
    N = len(A)
 
    # Function Call
    countPairs(A, N)
 
    # This code is contributed by chitranayal.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to count the number of
  // pairs (i, j) their Bitwise OR is
  // greater than Bitwise AND
  static void countPairs(int[] A, int n)
  {
 
    // Total number of pairs
    // possible from the array
    long count = (n * (n - 1)) / 2;
 
    // Stores frequency of each array element
    Dictionary<long, long> ump = new Dictionary<long, long>();
 
    // Traverse the array A[]
    for (int i = 0; i < n; i++)
    {
 
      // Increment ump[A[i]] by 1
      if(ump.ContainsKey(A[i]))
      {
        ump[A[i]]++;
      }
      else{
        ump[A[i]] = 1;
      }
    }
 
    // Traverse the Hashmap ump
    foreach(KeyValuePair<long, long> it in ump)
    {
 
      // Subtract those pairs (i, j)
      // from count which has the
      // same element on index i
      // and j (i < j)
      long c = it.Value;
      count = count - (c * (c - 1)) / 2;
    }
 
    // Print the result
    Console.WriteLine(count);
  }
 
  // Driver code
  static void Main() {
    int[] A = { 1, 4, 7 };
    int N = A.Length;
 
    // Function Call
    countPairs(A, N);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
// Javascript program for the above approach
 
  // Function to count the number of
  // pairs (i, j) their Bitwise OR is
  // greater than Bitwise AND
  function countPairs(A, n)
  {
 
    // Total number of pairs
    // possible from the array
    var count = (n * (n - 1)) / 2;
 
    // Stores frequency of each array element
    var ump = new Map();
 
    // Traverse the array A[]
    for (var i = 0; i < n; i++)
    {
 
      // Increment ump[A[i]] by 1
      if(ump.has(A[i]))
      {
        ump.set(A[i], ump.get(A[i])+1);
      }
      else{
        ump.set(A[i], 1);
      }
    }
 
    // Traverse the Hashmap ump
    for(var it of ump)
    {
 
      // Subtract those pairs (i, j)
      // from count which has the
      // same element on index i
      // and j (i < j)
      var c = it[1];
      count = count - (c * (c - 1)) / 2;
    }
 
    // Print the result
    document.write(count + "<br>");
  }
 
  // Driver code
    var A = [1, 4, 7];
    var N = A.length;
 
    // Function Call
    countPairs(A, N);
 
// This code is contributed by rutvik_56.
</script>

3

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