Contar pares con Odd XOR

Dada una array de n enteros. Averigüe el número de pares en la array cuyo XOR es impar.

Ejemplos: 

Input : arr[] = { 1, 2, 3 }
Output : 2
All pairs of array
1 ^ 2 = 3
1 ^ 3 = 2
2 ^ 3 = 1

Input : arr[] = { 1, 2, 3, 4 }
Output : 4

Enfoque ingenuo: podemos encontrar pares cuyo XOR sea impar ejecutando dos bucles. Si XOR de dos números es impar, aumente el número de pares.

Implementación:

C++

// C++ program to count pairs in array
// whose XOR is odd
#include <iostream>
using namespace std;
 
// A function will return number of pair
// whose XOR is odd
int countXorPair(int arr[], int n)
{
    // To store count of XOR pair
    int count = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
 
            // If XOR is odd increase count
            if ((arr[i] ^ arr[j]) % 2 == 1)
                count++;
    }
 
    // Return count
    return count;
}
 
// Driver program to test countXorPair()
int main()
{
    int arr[] = { 1, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countXorPair(arr, n);
 
    return 0;
}

Java

// Java program to count pairs in array whose
// XOR is odd
public class CountXor {
    // A function will return number of pair
    // whose XOR is odd
    static int countXorPair(int arr[], int n)
    {
        // To store count of XOR pair
        int count = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++)
 
                // If XOR is odd increase count
                if ((arr[i] ^ arr[j]) % 2 == 1)
                    count++;
        }
 
        // Return count
        return count;
    }
 
    // Driver program to test countXorPair()
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3 };
        System.out.println(countXorPair(arr, arr.length));
    }
}

Python 3

# Python 3 program to count
# pairs in array whose XOR is odd
 
# A function will
# return number of pair
# whose XOR is odd
def countXorPair(arr, n):
 
    # To store count of XOR pair
    count = 0
 
    for i in range(n):
        for j in range(i + 1, n):
 
            # If XOR is odd increase count
            if ((arr[i] ^ arr[j]) % 2 == 1):
                count += 1
 
    # Return count
    return count
 
# Driver Code
if __name__ == "__main__":
    arr= [ 1, 2, 3 ]
    n = len(arr)
    print(countXorPair(arr, n))
 
# This code is contributed
# by ChitraNayal

C#

// C# program to count pairs in
// array whose XOR is odd
using System;
 
public class CountXor {
     
    // A function will return number of pair
    // whose XOR is odd
    static int countXorPair(int[] arr, int n)
    {
        // To store count of XOR pair
        int count = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++)
 
                // If XOR is odd increase count
                if ((arr[i] ^ arr[j]) % 2 == 1)
                    count++;
        }
 
        // Return count
        return count;
    }
 
    // Driver program to test countXorPair()
    public static void Main()
    {
        int[] arr = {1, 2, 3};
        Console.WriteLine(countXorPair(arr, arr.Length));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to count
// pairs in array
// whose XOR is odd
 
// A function will
// return number of pair
// whose XOR is odd
function countXorPair($arr,$n)
{
 
    // To store count
    // of XOR pair
    $count = 0;
 
    for ($i = 0; $i < $n; $i++)
    {
        for ($j = $i + 1; $j < $n; $j++)
 
            // If XOR is odd
            // increase count
            if (($arr[$i] ^ $arr[$j]) % 2 == 1)
                $count++;
    }
 
    // Return count
    return $count;
}
 
    // Driver Code
    $arr = array(1, 2, 3);
    $n = count($arr);
    echo countXorPair($arr, $n);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
    // Javascript program to count pairs in
    // array whose XOR is odd
     
    // A function will return number of pair
    // whose XOR is odd
    function countXorPair(arr, n)
    {
        // To store count of XOR pair
        let count = 0;
   
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++)
   
                // If XOR is odd increase count
                if ((arr[i] ^ arr[j]) % 2 == 1)
                    count++;
        }
   
        // Return count
        return count;
    }
     
    let arr = [1, 2, 3];
      document.write(countXorPair(arr, arr.length));
     
</script>
Producción

2

Complejidad de tiempo: O(n*n)
Complejidad de espacio – O(1)

Enfoque Eficiente: Podemos observar que: 

odd ^ odd = even
odd ^ even = odd
even ^ odd = odd
even ^ even = even

Por lo tanto, el total de pares en una array cuyo XOR es impar será igual al conteo de números impares multiplicado por el conteo de números pares.

Implementación:

C++

// C++ program to count pairs in array
// whose XOR is odd
#include <iostream>
using namespace std;
 
// A function will return number of pair
// whose XOR is odd
int countXorPair(int arr[], int n)
{
    // To store count of odd and even
    // numbers
    int odd = 0, even = 0;
 
    for (int i = 0; i < n; i++) {
        // Increase even if number is
        // even otherwise increase odd
        if (arr[i] % 2 == 0)
            even++;
        else
            odd++;
    }
 
    // Return number of pairs
    return odd * even;
}
 
// Driver program to test countXorPair()
int main()
{
    int arr[] = { 1, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countXorPair(arr, n);
 
    return 0;
}

Java

// Java program to count pairs in array whose
// XOR is odd
 
public class CountXor {
    // A function will return number of pair
    // whose XOR is odd
    static int countXorPair(int arr[], int n)
    {
        // To store count of odd and even numbers
        int odd = 0, even = 0;
 
        for (int i = 0; i < n; i++) {
            // Increase even if number is
            // even otherwise increase odd
            if (arr[i] % 2 == 0)
                even++;
            else
                odd++;
        }
 
        // Return number of pairs
        return odd * even;
    }
 
    // Driver program to test countXorPair()
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3 };
        System.out.println(countXorPair(arr, arr.length));
    }
}

Python 3

# Python 3 program to count
# pairs in array whose XOR is odd
 
# A function will
# return number of pair
# whose XOR is odd
def countXorPair(arr, n):
 
    # To store count of
    # odd and even numbers
    odd = 0
    even = 0
 
    for i in range(n):
         
        # Increase even if number is
        # even otherwise increase odd
        if arr[i] % 2 == 0:
            even += 1
        else:
            odd += 1
 
    # Return number of pairs
    return odd * even
 
# Driver Code
if __name__ == "__main__":
    arr = [ 1, 2, 3 ]
    n = len(arr)
    print(countXorPair(arr, n))
 
# This code is contributed
# by ChitraNayal

C#

// C# program to count pairs in
// array whose XOR is odd
using System;
 
public class CountXor {
     
    // A function will return number of pair
    // whose XOR is odd
    static int countXorPair(int[] arr, int n)
    {
        // To store count of odd and even numbers
        int odd = 0, even = 0;
 
        for (int i = 0; i < n; i++) {
             
            // Increase even if number is
            // even otherwise increase odd
            if (arr[i] % 2 == 0)
                even++;
            else
                odd++;
        }
 
        // Return number of pairs
        return odd * even;
    }
 
    // Driver program to test countXorPair()
    public static void Main()
    {
        int[] arr = {1, 2, 3};
        Console.WriteLine(countXorPair(arr, arr.Length));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to count pairs in array
// whose XOR is odd
 
// A function will return number of pair
// whose XOR is odd
 
function countXorPair($arr, $n)
{
    // To store count of odd
    // and even numbers
    $odd = 0;
    $even = 0;
 
    for ($i = 0; $i < $n; $i++)
    {
        // Increase even if number is
        // even otherwise increase odd
        if ($arr[$i] % 2 == 0)
            $even++;
        else
            $odd++;
    }
 
    // Return number of pairs
    return $odd * $even;
}
 
// Driver Code
$arr = array( 1, 2, 3 );
$n = sizeof($arr);
echo countXorPair($arr, $n);
 
// This code is contributed by Ajit_m
?>

Javascript

<script>
// Javascript program to count pairs in array whose
// XOR is odd
 
    // A function will return number of pair
    // whose XOR is odd
    function countXorPair(arr, n)
    {
     
        // To store count of odd and even numbers
        let odd = 0, even = 0;
   
        for (let i = 0; i < n; i++)
        {
         
            // Increase even if number is
            // even otherwise increase odd
            if (arr[i] % 2 == 0)
                even++;
            else
                odd++;
        }
   
        // Return number of pairs
        return odd * even;
    }
     
    // Driver program to test countXorPair()
    let arr=[ 1, 2, 3 ];
    document.write(countXorPair(arr, arr.length));
     
    // This code is contributed by rag2127
</script>
Producción

2

Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)

Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

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