Cuente los pares ordenados de elementos de array de modo que AND bit a bit de K y XOR del par sea 0

Dada una array arr[] de tamaño N y un entero K , la tarea es encontrar el recuento de todos los pares ordenados ( i, j ) donde i != j , tal que ((arr[i] ⊕ arr[j] ) y K) = 0 . El ⊕ representa XOR bit a bit y & representa AND bit a bit.

Ejemplos :

Entrada : arr = [1, 2, 3, 4, 5], K = 3
Salida : 2
Explicación : Hay 2 pares que satisfacen la condición. 
Estos pares son: (1, 5) y (5, 1)

Entrada : arr = [5, 9, 24], K = 7
Salida : 0
Explicación : No existe tal par que satisfaga la condición.

Enfoque : El problema dado se puede resolver con la ayuda de la siguiente idea:

Usando la propiedad distributiva, podemos escribir ((arr[i] ⊕ arr[j]) & K) = ((arr[i] & K) ⊕ (arr[j] & K)) . 
Dado que para ((arr[i] & K) ⊕ (arr[j] & K)) = 0, estos dos términos (arr[i] & K) y (arr[j] & K) deben ser iguales.

Siga los pasos a continuación para resolver el problema:

• Cree un mapa y una variable de respuesta (digamos Res = 0 ).
• Recorra la array e inserte ( arr[i] & K ) para mapear con su conteo.
• Ahora, recorra el mapa y para cada entrada, si hay X ocurrencias de este tipo, entonces posibles pares = X*(X-1) . Entonces agregue eso al valor Res .
• Devuelva Res como la respuesta requerida.

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 find pair satisfying the condition
int findPair(int* arr, int N, int K)
{
    map<int, int> Mp;
    int Res = 0;
    for (int i = 0; i < N; i++)
        Mp[arr[i] & K]++;
 
    for (auto i : Mp)
        Res += ((i.second - 1) * i.second);
 
    return Res;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
 
    // Function call
    cout << findPair(arr, N, K) << endl;
    return 0;
}

// Java code to implement the above approach
import java.util.*;
 
class GFG {
 
  // Function to find pair satisfying the condition
  static int findPair(int arr[], int N, int K)
  {
    Map<Integer, Integer> mp = new HashMap<>();
    int Res = 0;
 
    for (int i = 0; i < N; i++)
    {
      if (mp.containsKey((arr[i] & K)))
      {
        mp.put((arr[i] & K), mp.get((arr[i] & K)) + 1);
      }
      else
      {
        mp.put((arr[i] & K), 1);
      }
    }
    for (Map.Entry<Integer, Integer> i : mp.entrySet())
    {
      Res += ((i.getValue() - 1) * i.getValue());
    }
 
    return Res;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = arr.length;
    int K = 3;
 
    // Function call
    System.out.println(findPair(arr, N, K));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python3 code to implement the above approach
 
# Function to find pair satisfying the condition
def findPair(arr, N, K) :
    Mp = {};
    Res = 0;
 
    for i in range(N) :
        Mp[arr[i] & K] = Mp.get(arr[i] & K, 0) + 1;
 
    for i in Mp:
        Res += ((Mp[i] - 1) * Mp[i]);
 
    return Res;
 
 
# Driver Code
if __name__ == "__main__" :
    arr = [ 1, 2, 3, 4, 5 ];
    N = len(arr);
    K = 3;
 
    # Function call
    print(findPair(arr, N, K));
     
    # This code is contributed by AnkThon

using System;
using System.Collections.Generic;
public class GFG{
   
  // Function to find pair satisfying the condition
public static int findPair(int[] arr, int N, int K)
{
    SortedDictionary<int,int>Mp=
            new SortedDictionary<int,int>();
    int Res = 0;
   
  // Initialising Mp with 0
  for(int i=0;i<N;i++)
  {
    Mp[i] = 0;
  }
 
    for (int i = 0; i < N; i++)
        Mp[(arr[i] & K)]++;
 
   
     foreach( KeyValuePair<int,int> kvp in Mp )
        {
            Res+=(( kvp.Value - 1) *  kvp.Value);
        }
 
    return Res;
}
 
 
    static public void Main (){
 
        int[] arr = { 1, 2, 3, 4, 5 };
    int N =arr.Length;
    int K = 3;
 
    // Function call
    Console.WriteLine( findPair(arr, N, K) );
    }
}
 
// This code is contributed by akashish__

<script>
        // JavaScript code for the above approach
 
        // Function to find pair satisfying the condition
        function findPair(arr, N, K) {
            let Mp = new Map();
            let Res = 0;
 
            for (let i = 0; i < N; i++) {
                Mp[arr[i] & K]++;
 
                if (Mp.has(arr[i] & K)) {
                    Mp.set(arr[i] & K, Mp.get(arr[i] & K) + 1)
                }
                else {
                    Mp.set(arr[i] & K, 1);
                }
            }
            for (let [key, val] of Mp)
                Res += ((val - 1) * val);
 
            return Res;
        }
 
        // Driver Code
 
        let arr = [1, 2, 3, 4, 5];
        let N = arr.length;
        let K = 3;
 
        // Function call
        document.write(findPair(arr, N, K) + '<br>');
 
    // This code is contributed by Potta Lokesh
    </script>

2

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