Recuento de pares de Array con una suma igual al doble de su AND bit a bit

Posted on by Rudeus Greyrat

Dada una array arr[] , la tarea es contar los pares en la array con una suma igual al doble de su AND bit a bit , es decir,  A + B = 2 * (A \& B)
Ejemplos: 
 

Entrada: arr[] = {1, 1, 3, 4, 4, 5, 7, 8} 
Salida: 2 
Explicación: 
Pares con suma igual al doble de sus bits Y: 
{(1, 1), (4, 4) }
Entrada: arr[] = {1, 3, 3, 5, 4, 6} 
Salida: 1 
 

Enfoque ingenuo: una solución simple es iterar sobre cada par posible y verificar que si la suma del par es igual al doble del AND bit a bit del par. Si el par tiene la misma suma y AND bit a bit, entonces incremente el conteo de dichos pares en 1.
Enfoque eficiente: La idea es usar la relación entre la suma y el AND bit a bit. Eso es – 
 

A + B = (A \^ B) + 2 * (A \& B)

En esto, para igual suma y AND bit a bit, el valor del XOR bit a bit del par debe ser igual a 0. Sabemos que el XOR bit a bit de dos pares cualesquiera es igual a 0 solo si son iguales entre sí. Por lo tanto, si X es la frecuencia del elemento. Luego incremente el conteo de pares en  ^{X}C_{2} .
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Map to store the
// occurrence of
// elements of array
map<int, int> mp;
 
// Function to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
int find_pairs(int ar[], int n)
{
    int ans = 0;
 
    // Loop to find the frequency
    // of elements of array
    for (int i = 0; i < n; i++) {
        mp[ar[i]]++;
    }
 
    // Function to find the count
    // such pairs in the array
    for (auto i : mp) {
        int count = i.second;
        if (count > 1) {
 
            // if an element occurs more
            // than once then the answer
            // will by incremented
            // by nC2 times
            ans += ((count
                     * (count - 1))
                    / 2);
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int ar[]
        = { 1, 2, 3, 3, 4,
            5, 5, 7, 8 };
    int arr_size = (sizeof(ar)
                    / sizeof(ar[0]));
 
    // Function Call
    cout << find_pairs(ar, arr_size);
    return 0;
}

Java

// Java implementation to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
import java.util.*;
 
class GFG{
 
// Map to store the
// occurrence of
// elements of array
static HashMap<Integer,
               Integer> mp = new HashMap<Integer,
                                         Integer>();
 
// Function to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
static int find_pairs(int arr[], int n)
{
    int ans = 0;
 
    // Loop to find the frequency
    // of elements of array
    for(int i = 0; i < n; i++)
    {
       if(mp.containsKey(arr[i]))
       {
           mp.put(arr[i], mp.get(arr[i]) + 1);
       }
       else
       {
           mp.put(arr[i], 1);
       }
    }
     
    // Function to find the count
    // such pairs in the array
    for(Map.Entry<Integer, Integer> i:mp.entrySet())
    {
       int count = i.getValue();
       if (count > 1)
       {
 
           // If an element occurs more
           // than once then the answer
           // will by incremented
           // by nC2 times
           ans += ((count * (count - 1)) / 2);
       }
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 3, 4,
                  5, 5, 7, 8 };
    int arr_size = arr.length;
 
    // Function Call
    System.out.print(find_pairs(arr, arr_size));
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 implementation to find the
# pairs with equal sum and twice the
# bitwise AND of the pairs
from collections import defaultdict
 
# Map to store the occurrence
# of elements of array
mp = defaultdict(int)
 
# Function to find the pairs
# with equal sum and twice the
# bitwise AND of the pairs
def find_pairs(arr, n):
 
    ans = 0
 
    # Loop to find the frequency
    # of elements of array
    for i in range(n):
        mp[arr[i]] += 1
 
    # Function to find the count
    # such pairs in the array
    for i in mp.values():
        count = i
        if (count > 1):
 
            # If an element occurs more
            # than once then the answer
            # will by incremented
            # by nC2 times
            ans += ((count * (count - 1)) // 2)
     
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 1, 2, 3, 3, 4,
            5, 5, 7, 8 ]
    arr_size = len(arr)
 
    # Function Call
    print(find_pairs(arr, arr_size))
 
# This code is contributed by chitranayal

C#

// C# implementation to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
using System;
using System.Collections.Generic;
 
class GFG{
 
// To store the occurrence
// of elements of array
static Dictionary<int,
                  int> mp = new Dictionary<int,
                                           int>();
 
// Function to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
static int find_pairs(int []arr, int n)
{
    int ans = 0;
 
    // Loop to find the frequency
    // of elements of array
    for(int i = 0; i < n; i++)
    {
       if(mp.ContainsKey(arr[i]))
       {
           mp[arr[i]] = mp[arr[i]] + 1;
       }
       else
       {
           mp.Add(arr[i], 1);
       }
    }
     
    // Function to find the count
    // such pairs in the array
    foreach(KeyValuePair<int, int> i in mp)
    {
       int count = i.Value;
       if (count > 1)
       {
            
           // If an element occurs more
           // than once then the answer
           // will by incremented
           // by nC2 times
           ans += ((count * (count - 1)) / 2);
       }
    }
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 3, 4,
                  5, 5, 7, 8 };
    int arr_size = arr.Length;
 
    // Function Call
    Console.Write(find_pairs(arr, arr_size));
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
 
// JavaScript implementation to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
 
// Map to store the
// occurrence of
// elements of array
let  mp = new Map();
 
// Function to find the pairs
// with equal sum and twice the
// bitwise AND of the pairs
function find_pairs(arr,n)
{
    let ans = 0;
   
    // Loop to find the frequency
    // of elements of array
    for(let i = 0; i < n; i++)
    {
       if(mp.has(arr[i]))
       {
           mp.set(arr[i], mp.get(arr[i]) + 1);
       }
       else
       {
           mp.set(arr[i], 1);
       }
    }
       
    // Function to find the count
    // such pairs in the array
    for(let [key, value] of mp.entries())
    {
       let count = value;
       if (count > 1)
       {
   
           // If an element occurs more
           // than once then the answer
           // will by incremented
           // by nC2 times
           ans += ((count * (count - 1)) / 2);
       }
    }
    return ans;
}
 
// Driver Code
let arr=[1, 2, 3, 3, 4,
                  5, 5, 7, 8];
                   
let arr_size = arr.length;
// Function Call
document.write(find_pairs(arr, arr_size));
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción: 

2

 

Publicación traducida automáticamente

Artículo escrito por vaibhav19verma 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 *