Total de pares distintos de dos arrays de modo que el segundo número se pueda obtener invirtiendo los bits del primero

Dadas dos arrays arr1[] y arr2[] , la tarea es tomar un elemento de la primera array (digamos a) y un elemento de la segunda array (digamos b) . Si el número formado al invertir los bits de a es igual a b , entonces el par (a, b) es un par válido. 
Ejemplo de inversión de bits:  
11 se escribe como 1011 en binario. Después de invertir sus bits, se obtiene 0100 que es 4 en decimal. Por lo tanto , (11, 4) es un par válido pero (4, 11) no lo es , ya que 11 no se puede obtener después de invertir los dígitos de4 es decir 100 -> 011 que es 3 .
Ejemplos: 
 

Entrada: arr1[] = {11, 5, 4}, arr2[] = {1, 4, 3, 11} 
Salida: 2 
(11, 4) y (4, 3) son los únicos pares válidos.
Entrada: arr1[] = {43, 7, 1, 99}, arr2 = {5, 1, 28, 20} 
Salida: 2 
 

Acercarse: 
 

• Tome dos conjuntos vacíos s1 y s2 .
• Inserte todos los elementos de arr2[] en s2 .
• Iterar la primera array. Si el elemento no está presente en el primer conjunto y el número formado al invertir sus bits está presente en el segundo conjunto, incremente el conteo e inserte el elemento actual en s1 para que no se vuelva a contar.
• Imprime el valor de conteo al final.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number formed
// by inverting bits the bits of num
int invertBits(int num)
{
    // Number of bits in num
    int x = log2(num) + 1;
 
    // Inverting the bits one by one
    for (int i = 0; i < x; i++)
        num = (num ^ (1 << i));
 
    return num;
}
 
// Function to return the total valid pairs
int totalPairs(int arr1[], int arr2[], int n, int m)
{
 
    // Set to store the elements of the arrays
    unordered_set<int> s1, s2;
 
    // Insert all the elements of arr2[] in the set
    for (int i = 0; i < m; i++)
        s2.insert(arr2[i]);
 
    // Initialize count variable to 0
    int count = 0;
    for (int i = 0; i < n; i++) {
 
        // Check if element of the first array
        // is not in the first set
        if (s1.find(arr1[i]) == s1.end()) {
 
            // Check if the element formed by inverting bits
            // is in the second set
            if (s2.find(invertBits(arr1[i])) != s2.end()) {
 
                // Increment the count of valid pairs and insert
                // the element in the first set so that
                // it doesn't get counted again
                count++;
                s1.insert(arr1[i]);
            }
        }
    }
 
    // Return the total number of pairs
    return count;
}
 
// Driver code
int main()
{
    int arr1[] = { 43, 7, 1, 99 };
    int arr2[] = { 5, 1, 28, 20 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
 
    cout << totalPairs(arr1, arr2, n, m);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
import java.io.*;
import java.lang.*;
 
class GFG
{
 
static int log2(int N)
{
    // calculate log2 N indirectly
    // using log() method
    int result = (int)(Math.log(N) / Math.log(2));
 
    return result;
}
 
// Function to return the number formed
// by inverting bits the bits of num
static int invertBits(int num)
{
    // Number of bits in num
    int x = log2(num) + 1;
 
    // Inverting the bits one by one
    for (int i = 0; i < x; i++)
        num = (num ^ (1 << i));
 
    return num;
}
 
// Function to return the total valid pairs
static int totalPairs(int arr1[], int arr2[], int n, int m)
{
 
    // Set to store the elements of the arrays
    HashSet<Integer> s1 = new HashSet<Integer>();
    HashSet<Integer> s2 = new HashSet<Integer>();
 
    // add all the elements of arr2[] in the set
    for (int i = 0; i < m; i++)
        s2.add(arr2[i]);
 
    // Initialize count variable to 0
    int count = 0;
    for (int i = 0; i < n; i++)
    {
 
        // Check if element of the first array
        // is not in the first set
        if (!s1.contains(arr1[i]))
        {
 
            // Check if the element formed by inverting bits
            // is in the second set
            if (s2.contains(invertBits(arr1[i])))
            {
 
                // Increment the count of valid pairs and add
                // the element in the first set so that
                // it doesn't get counted again
                count++;
                s1.add(arr1[i]);
            }
        }
    }
 
    // Return the total number of pairs
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int arr1[] = { 43, 7, 1, 99 };
    int arr2[] = { 5, 1, 28, 20 };
    int n = arr1.length;
    int m = arr2.length;
 
    System.out.println(totalPairs(arr1, arr2, n, m));
}
}
 
// This code is contributed by SHUBHAMSINGH10

# Python3 implementation of the approach
from math import log2;
 
# Function to return the number formed
# by inverting bits the bits of num
def invertBits(num) :
     
    # Number of bits in num
    x = log2(num) + 1;
 
    # Inverting the bits one by one
    for i in range(int(x)) :
        num = (num ^ (1 << i));
 
    return num;
 
# Function to return the total valid pairs
def totalPairs(arr1, arr2, n, m) :
 
    # Set to store the elements of the arrays
    s1, s2 = set(), set();
     
    # Insert all the elements of
    # arr2[] in the set
    for i in range(m) :
        s2.add(arr2[i]);
         
    # Initialize count variable to 0
    count = 0;
    for i in range(n) :
         
        # Check if element of the first array
        # is not in the first set
        if arr1[i] not in s1 :
             
            # Check if the element formed by
            # inverting bits is in the second set
            if invertBits(arr1[i]) in s2 :
                 
                # Increment the count of valid pairs
                # and insert the element in the first
                # set so that it doesn't get counted again
                count += 1;
                s1.add(arr1[i]);
     
    # Return the total number of pairs
    return count;
 
# Driver code
if __name__ == "__main__" :
 
    arr1 = [ 43, 7, 1, 99 ];
    arr2 = [ 5, 1, 28, 20 ];
    n = len(arr1);
    m = len(arr2);
 
    print(totalPairs(arr1, arr2, n, m));
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
  
static int log2(int N)
{
    // calculate log2 N indirectly
    // using log() method
    int result = (int)(Math.Log(N) / Math.Log(2));
  
    return result;
}
  
// Function to return the number formed
// by inverting bits the bits of num
static int invertBits(int num)
{
    // Number of bits in num
    int x = log2(num) + 1;
  
    // Inverting the bits one by one
    for (int i = 0; i < x; i++)
        num = (num ^ (1 << i));
  
    return num;
}
  
// Function to return the total valid pairs
static int totalPairs(int []arr1, int []arr2, int n, int m)
{
  
    // Set to store the elements of the arrays
    HashSet<int> s1 = new HashSet<int>();
    HashSet<int> s2 = new HashSet<int>();
  
    // add all the elements of arr2[] in the set
    for (int i = 0; i < m; i++)
        s2.Add(arr2[i]);
  
    // Initialize count variable to 0
    int count = 0;
    for (int i = 0; i < n; i++)
    {
  
        // Check if element of the first array
        // is not in the first set
        if (!s1.Contains(arr1[i]))
        {
  
            // Check if the element formed by inverting bits
            // is in the second set
            if (s2.Contains(invertBits(arr1[i])))
            {
  
                // Increment the count of valid pairs and add
                // the element in the first set so that
                // it doesn't get counted again
                count++;
                s1.Add(arr1[i]);
            }
        }
    }
  
    // Return the total number of pairs
    return count;
}
  
// Driver code
public static void Main()
{
    int []arr1 = { 43, 7, 1, 99 };
    int []arr2 = { 5, 1, 28, 20 };
    int n = arr1.Length;
    int m = arr2.Length;
  
    Console.Write(totalPairs(arr1, arr2, n, m));
}
}
  
// This code is contribute by chitranayal

<script>
 
// Javascript implementation of the approach
 
// Function to return the number formed
// by inverting bits the bits of num
function invertBits(num)
{
    // Number of bits in num
    var x = parseInt(Math.log2(num)) + 1;
 
    // Inverting the bits one by one
    for (var i = 0; i < x; i++)
        num = (num ^ (1 << i));
 
    return num;
}
 
// Function to return the total valid pairs
function totalPairs(arr1, arr2, n, m)
{
 
    // Set to store the elements of the arrays
    var s1 = new Set();
    var s2 = new Set();
 
    // add all the elements of arr2[] in the set
    for (var i = 0; i < m; i++)
        s2.add(arr2[i]);
 
    // Initialize count variable to 0
    var count = 0;
    for (var i = 0; i < n; i++) {
 
        // Check if element of the first array
        // is not in the first set
        if (!s1.has(arr1[i]))
        {
            // Check if the element formed by inverting bits
            // is in the second set
            if (s2.has(invertBits(arr1[i]))) {
 
                // Increment the count of valid pairs and add
                // the element in the first set so that
                // it doesn't get counted again
                count++;
                s1.add(arr1[i]);
            }
        }
    }
 
    // Return the total number of pairs
    return count;
}
 
// Driver code
var arr1 = [43, 7, 1, 99];
var arr2 = [5, 1, 28, 20];
var n = arr1.length;
var m = arr2.length;
document.write( totalPairs(arr1, arr2, n, m));
 
 
</script>

2

Complejidad temporal: O(n+m)

Espacio Auxiliar: O(n+m)