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