Pares totales en una array tal que el AND bit a bit, el OR bit a bit y el XOR bit a bit de LSB es 1

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N . La tarea es encontrar el número de pares (arr[i], arr[j]) como cntAND , cntOR y cntXOR tal que: 

  1. cntAND: Recuento de pares donde AND bit a bit de bits menos significativos es 1.
  2. cntOR: Recuento de pares donde OR bit a bit de bits menos significativos es 1.
  3. cntXOR: Recuento de pares donde el XOR bit a bit de bits menos significativos es 1.

Ejemplos: 

Entrada: arr[] = {1, 2, 3} 
Salida: 
cntXOR = 2 
cntAND = 1 
cntOR = 3 
Los elementos de la array en binario son {01, 10, 11} 
Total de pares XOR: 2, es decir, (1, 2) y ( 2, 3) 
Total de pares AND: 1, es decir, (1, 3) 
Total de pares OR: 3, es decir, (1, 2), (2, 3) y (1, 3)

Entrada: arr[] = {1, 3, 4, 2} 
Salida: 
cntXOR = 4 
cntAND = 1 
cntOR = 5 

Acercarse: 

  1. Para obtener el LSB de los elementos del arreglo, primero calculamos el total de elementos pares e impares. Los elementos pares tienen LSB como 0 y los elementos impares tienen LSB como 1.
  2. Para poder 
    • XOR para ser 1 , LSB de ambos elementos tiene que ser diferente.
    • Y para ser 1 , LSB de ambos elementos tiene que ser 1.
    • O para ser 1 , al menos uno de los elementos debe tener su LSB como 1.
  3. Por lo tanto, el número total de pares requeridos 
    • Para XOR: cntXOR = cntOdd * cntEven
    • Para AND: cntAND = cntOdd * (cntOdd – 1) / 2
    • Para OR: cntOR = (cntOdd * cntEven) + cntOdd * (cntOdd – 1) / 2

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of required pairs
void CalculatePairs(int a[], int n)
{
 
    // To store the count of elements which
    // give remainder 0 i.e. even values
    int cnt_zero = 0;
 
    // To store the count of elements which
    // give remainder 1 i.e. odd values
    int cnt_one = 0;
 
    for (int i = 0; i < n; i++) {
 
        if (a[i] % 2 == 0)
            cnt_zero += 1;
        else
            cnt_one += 1;
    }
 
    long int total_XOR_pairs = cnt_zero * cnt_one;
    long int total_AND_pairs = (cnt_one) * (cnt_one - 1) / 2;
    long int total_OR_pairs = cnt_zero * cnt_one
                              + (cnt_one) * (cnt_one - 1) / 2;
 
    cout << "cntXOR = " << total_XOR_pairs << endl;
    cout << "cntAND = " << total_AND_pairs << endl;
    cout << "cntOR = " << total_OR_pairs << endl;
}
 
// Driver code
int main()
{
    int a[] = { 1, 3, 4, 2 };
    int n = sizeof(a) / sizeof(a[0]);
 
    CalculatePairs(a, n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG {
 
    // Function to find the count of required pairs
    static void CalculatePairs(int a[], int n)
    {
 
        // To store the count of elements which
        // give remainder 0 i.e. even values
        int cnt_zero = 0;
 
        // To store the count of elements which
        // give remainder 1 i.e. odd values
        int cnt_one = 0;
 
        for (int i = 0; i < n; i++) {
 
            if (a[i] % 2 == 0)
                cnt_zero += 1;
            else
                cnt_one += 1;
        }
 
        int total_XOR_pairs = cnt_zero * cnt_one;
        int total_AND_pairs = (cnt_one) * (cnt_one - 1) / 2;
        int total_OR_pairs = cnt_zero * cnt_one
                             + (cnt_one) * (cnt_one - 1) / 2;
 
        System.out.println("cntXOR = " + total_XOR_pairs);
        System.out.println("cntAND = " + total_AND_pairs);
        System.out.println("cntOR = " + total_OR_pairs);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 1, 3, 4, 2 };
        int n = a.length;
 
        CalculatePairs(a, n);
    }
}

Python3

# Python3 program to find number of pairs
 
# Function to find the count of required pairs
def CalculatePairs(a, n):
 
    # To store the count of elements which
    # give remainder 0 i.e. even values
    cnt_zero = 0
 
    # To store the count of elements which
    # give remainder 1 i.e. odd values
    cnt_one = 0
 
    for i in range(0, n):
        if (a[i] % 2 == 0):
            cnt_zero += 1
        else:
            cnt_one += 1
     
    total_XOR_pairs = cnt_zero * cnt_one
    total_AND_pairs = (cnt_one) * (cnt_one - 1) / 2
    total_OR_pairs = cnt_zero * cnt_one + (cnt_one) * (cnt_one - 1) / 2
 
    print("cntXOR = ", int(total_XOR_pairs))
    print("cntAND = ", int(total_AND_pairs))
    print("cntOR = ", int(total_OR_pairs))
     
 
# Driver code
if __name__ == '__main__':
     
    a = [1, 3, 4, 2]
    n = len(a)
     
    # Print the count
    CalculatePairs(a, n)

C#

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function to find the count of required pairs
    static void CalculatePairs(int[] a, int n)
    {
 
        // To store the count of elements which
        // give remainder 0 i.e. even values
        int cnt_zero = 0;
 
        // To store the count of elements which
        // give remainder 1 i.e. odd values
        int cnt_one = 0;
 
        for (int i = 0; i < n; i++) {
 
            if (a[i] % 2 == 0)
                cnt_zero += 1;
            else
                cnt_one += 1;
        }
 
        int total_XOR_pairs = cnt_zero * cnt_one;
        int total_AND_pairs = (cnt_one) * (cnt_one - 1) / 2;
        int total_OR_pairs = cnt_zero * cnt_one
                             + (cnt_one) * (cnt_one - 1) / 2;
 
        Console.WriteLine("cntXOR = " + total_XOR_pairs);
        Console.WriteLine("cntAND = " + total_AND_pairs);
        Console.WriteLine("cntOR = " + total_OR_pairs);
    }
 
    // Driver code
    public static void Main()
    {
        int[] a = { 1, 3, 4, 2 };
        int n = a.Length;
 
        // Print the count
        CalculatePairs(a, n);
    }
}

PHP

<?php
// PHP implementation of the approach
 
// Function to find the count of required pairs
function CalculatePairs($a, $n)
{
 
    // To store the count of elements which
    // give remainder 0 i.e. even values
    $cnt_zero = 0;
 
    // To store the count of elements which
    // give remainder 1 i.e. odd values
    $cnt_one = 0;
 
    for ($i = 0; $i < $n; $i++) {
 
        if ($a[$i] % 2 == 0)
            $cnt_zero += 1;
        else
            $cnt_one += 1;
    }
     
    $total_XOR_pairs = $cnt_zero * $cnt_one;
    $total_AND_pairs = ($cnt_one) * ($cnt_one - 1) / 2;
    $total_OR_pairs = $cnt_zero * $cnt_one
+ ($cnt_one) * ($cnt_one - 1) / 2;
 
    echo("cntXOR = $total_XOR_pairs\n");
    echo("cntAND = $total_AND_pairs\n");
    echo("cntOR = $total_OR_pairs\n");
}
 
// Driver code
$a = array(1, 3, 4, 2);
$n = count($a);
 
// Print the count
CalculatePairs($a, $n);
?>

Javascript

<script>
 
// JavaScript implementation of the approach
 
// Function to find the count of required pairs
function CalculatePairs(a, n)
{
 
    // To store the count of elements which
    // give remainder 0 i.e. even values
    let cnt_zero = 0;
 
    // To store the count of elements which
    // give remainder 1 i.e. odd values
    let cnt_one = 0;
 
    for (let i = 0; i < n; i++) {
 
        if (a[i] % 2 == 0)
            cnt_zero += 1;
        else
            cnt_one += 1;
    }
 
    let total_XOR_pairs = cnt_zero * cnt_one;
    let total_AND_pairs = (cnt_one) * (cnt_one - 1) / 2;
    let total_OR_pairs = cnt_zero * cnt_one
                            + (cnt_one) * (cnt_one - 1) / 2;
 
    document.write("cntXOR = " + total_XOR_pairs + "<br>");
    document.write("cntAND = " + total_AND_pairs + "<br>");
    document.write("cntOR = " + total_OR_pairs + "<br>");
}
 
// Driver code
 
    let a = [ 1, 3, 4, 2 ];
    let n = a.length;
 
    CalculatePairs(a, n);
 
// This code is contributed by Surbhi Tyagi
 
</script>
Producción

cntXOR = 4
cntAND = 1
cntOR = 5

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

Publicación traducida automáticamente

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