Maximice el recuento de pares cuyo AND bit a bit supere el XOR bit a bit reemplazando dichos pares con su AND bit a bit

Dada una array arr[] que consta de N enteros positivos, reemplace los pares de elementos de la array cuyo AND bit a bit exceda los valores XOR bit a bit por su valor AND bit a bit. Finalmente, cuente el número máximo de dichos pares que se pueden generar a partir de la array.

Ejemplos:

Entrada: arr[] = {12, 9, 15, 7}
Salida: 2
Explicación:
Paso 1: Seleccione el par {12, 15} y reemplace el par por su AND bit a bit (= 12). La array arr[] se modifica a {12, 9, 7}. 
Paso 2: Reemplace el par {12, 9} por su AND bit a bit (= 8). Por lo tanto, la array arr[] se modifica a {8, 7}. 
Por lo tanto, el número máximo de dichos pares es 2.

Entrada: arr[] = {2, 6, 12, 18, 9}
Salida: 1

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los pares posibles y seleccionar un par que tenga AND bit a bit mayor que su XOR bit a bit . Reemplace el par e inserte su Bitwise AND . Repita el proceso anterior hasta que no se encuentren tales pares. Imprime el recuento de dichos pares obtenidos. 
Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

• Un número que tiene su bit más significativo en la i- ^ésima posición sólo puede formar un par con otros números que tienen MSB en la i- ^ésima posición.
• El recuento total de números que tienen su MSB en la i- ^ésima posición disminuye en uno si se selecciona uno de estos pares.
• Por lo tanto, los pares totales que se pueden formar en la i- ^ésima posición son el recuento total de números que tienen MB en la i- ^ésima posición disminuido en 1 .

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

• Inicialice un Map , digamos freq , para almacenar el conteo de números que tienen MSB en las respectivas posiciones de bit.
• Recorra la array y para cada elemento de la array arr[i] , encuentre el MSB de arr[i] e incremente el conteo de MSB en la frecuencia en 1 .
• Inicialice una variable, digamos pares , para almacenar el recuento de pares totales.
• Recorra el mapa y actualice los pares como pares += (freq[i] – 1) .
• Después de completar los pasos anteriores, imprima el valor de los pares 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 whose Bitwise AND is
// greater than the Bitwise XOR
int countPairs(int arr[], int N)
{
    // Stores the frequency of
    // MSB of array elements
    unordered_map<int, int> freq;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Increment count of numbers
        // having MSB at log(arr[i])
        freq[log2(arr[i])]++;
    }
 
    // Stores total number of pairs
    int pairs = 0;
 
    // Traverse the Map
    for (auto i : freq) {
        pairs += i.second - 1;
    }
 
    // Return total count of pairs
    return pairs;
}
 
// Driver Code
int main()
{
    int arr[] = { 12, 9, 15, 7 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << countPairs(arr, N);
 
    return 0;
}

// C# program for the above approach
import java.util.*;
class GFG {
 
  // Function to count the number of
  // pairs whose Bitwise AND is
  // greater than the Bitwise XOR
  static int countPairs(int[] arr, int N)
  {
 
    // Stores the frequency of
    // MSB of array elements
    HashMap<Integer, Integer> freq
      = new HashMap<Integer, Integer>();
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
      // Increment count of numbers
      // having MSB at log(arr[i])
      if (freq.containsKey((int)(Math.log(arr[i]))))
        freq.put((int)(Math.log(arr[i])),
                 (int)(Math.log(arr[i])) + 1);
      else
        freq.put((int)(Math.log(arr[i])), 1);
    }
 
    // Stores total number of pairs
    int pairs = 0;
 
    // Traverse the Map
    for (Map.Entry<Integer, Integer> item :
         freq.entrySet())
 
    {
      pairs += item.getValue() - 1;
    }
 
    // Return total count of pairs
    return pairs;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 12, 9, 15, 7 };
    int N = arr.length;
    System.out.println(countPairs(arr, N));
  }
}
 
// This code is contributed by ukasp.

# Python3 program for the above approach
from math import log2
 
# Function to count the number of
# pairs whose Bitwise AND is
# greater than the Bitwise XOR
def countPairs(arr, N):
   
    # Stores the frequency of
    # MSB of array elements
    freq = {}
 
    # Traverse the array
    for i in range(N):
 
        # Increment count of numbers
        # having MSB at log(arr[i])
        x = int(log2(arr[i]))
        freq[x] = freq.get(x, 0) + 1
 
    # Stores total number of pairs
    pairs = 0
 
    # Traverse the Map
    for i in freq:
        pairs += freq[i] - 1
 
    # Return total count of pairs
    return pairs
 
# Driver Code
if __name__ == '__main__':
    arr = [12, 9, 15, 7]
    N = len(arr)
    print(countPairs(arr, N))
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
// Function to count the number of
// pairs whose Bitwise AND is
// greater than the Bitwise XOR
static int countPairs(int []arr, int N)
{
   
    // Stores the frequency of
    // MSB of array elements
    Dictionary<int,int> freq = new Dictionary<int,int>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
        // Increment count of numbers
        // having MSB at log(arr[i])
        if(freq.ContainsKey((int)(Math.Log(Convert.ToDouble(arr[i]),2.0))))
         freq[(int)(Math.Log(Convert.ToDouble(arr[i]),2.0))]++;
        else
          freq[(int)(Math.Log(Convert.ToDouble(arr[i]),2.0))] = 1;
    }
 
    // Stores total number of pairs
    int pairs = 0;
 
    // Traverse the Map
    foreach(var item in freq)
    {
        pairs += item.Value - 1;
    }
 
    // Return total count of pairs
    return pairs;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 12, 9, 15, 7 };
    int N =  arr.Length;
    Console.WriteLine(countPairs(arr, N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
 
// Javascript program for the above approach
 
// Function to count the number of
// pairs whose Bitwise AND is
// greater than the Bitwise XOR
function countPairs(arr, N)
{
    // Stores the frequency of
    // MSB of array elements
    var freq = new Map();
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // Increment count of numbers
        // having MSB at log(arr[i])
        if(freq.has(parseInt(Math.log2(arr[i]))))
        {
            freq.set(parseInt(Math.log2(arr[i])), freq.get(parseInt(Math.log2(arr[i])))+1);
        }
        else
        {
            freq.set(parseInt(Math.log2(arr[i])), 1);
        }
    }
 
    // Stores total number of pairs
    var pairs = 0;
 
    // Traverse the Map
    freq.forEach((value,key) => {
        pairs += value - 1;
    });
 
    // Return total count of pairs
    return pairs;
}
 
// Driver Code
var arr = [12, 9, 15, 7 ];
var N = arr.length;
document.write( countPairs(arr, N));
 
</script>

2

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