Dada una array ![A[ ]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-b52b1a8f2ae43b3b99cd93fc7c68eb23_l3.png "Rendered by QuickLaTeX.com")
de tamaño N. Encuentre el número de pares (i, j) tales que 
XOR 
= 0 y 1 <= i < j <= N.
Ejemplos:
Input : A[] = {1, 3, 4, 1, 4}
Output : 2
Explanation : Index (0, 3) and (2, 4)
Input : A[] = {2, 2, 2}
Output : 3
Primer enfoque : Ordenar XOR = 0 solo se cumple cuando 
. Por lo tanto, primero ordenaremos la array y luego contaremos la frecuencia de cada elemento. Por combinatoria, podemos observar que si la frecuencia de algún elemento es 
entonces, contribuirá 
a la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of pairs in an array such that
// their XOR is 0
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the count
int calculate(int a[], int n)
{
// Sorting the list using built in function
sort(a, a + n);
int count = 1;
int answer = 0;
// Traversing through the elements
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1])
// Counting frequency of each elements
count += 1;
else {
// Adding the contribution of the frequency to
// the answer
answer = answer + (count * (count - 1)) / 2;
count = 1;
}
}
answer = answer + (count * (count - 1)) / 2;
return answer;
}
// Driver Code
int main()
{
int a[] = { 1, 2, 1, 2, 4 };
int n = sizeof(a) / sizeof(a[0]);
cout << calculate(a, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find number of pairs in an array such that
// their XOR is 0
#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
// Function to calculate the count
int calculate(int a[], int n)
{
// Sorting the list using built in function
qsort(a, n, sizeof(int), cmpfunc);
int count = 1;
int answer = 0;
// Traversing through the elements
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1])
// Counting frequency of each elements
count += 1;
else {
// Adding the contribution of the frequency to
// the answer
answer = answer + (count * (count - 1)) / 2;
count = 1;
}
}
answer = answer + (count * (count - 1)) / 2;
return answer;
}
// Driver Code
int main()
{
int a[] = { 1, 2, 1, 2, 4 };
int n = sizeof(a) / sizeof(a[0]);
printf("%d", calculate(a, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find number of pairs in an array suchthat
// their XOR is 0
import java.util.*;
class GFG {
// Function to calculate the count
static int calculate(int a[], int n)
{
// Sorting the list using built in function
Arrays.sort(a);
int count = 1;
int answer = 0;
for (int i = 1; i < n; i++) {
// Counting frequency of each elements
if (a[i] == a[i - 1])
count += 1;
else {
// Adding the contribution of the frequency
// to the answer
answer = answer + (count * (count - 1)) / 2;
count = 1;
}
}
answer = answer + (count * (count - 1)) / 2;
return answer;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, 1, 2, 4 };
int n = a.length;
System.out.println(calculate(a, n));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to find number of pairs # in an array such that their XOR is 0 # Function to calculate the count def calculate(a) : # Sorting the list using # built in function a.sort() count = 1 answer = 0 # Traversing through the elements for i in range(1, len(a)) : if a[i] == a[i - 1] : # Counting frequency of each elements count += 1 else : # Adding the contribution of # the frequency to the answer answer = answer + count * (count - 1) // 2 count = 1 answer = answer + count * (count - 1) // 2 return answer # Driver Code if __name__ == '__main__': a = [1, 2, 1, 2, 4] # Print the count print(calculate(a))
C#
// C# program to find number
// of pairs in an array such
// that their XOR is 0
using System;
class GFG
{
// Function to calculate
// the count
static int calculate(int []a, int n)
{
// Sorting the list using
// built in function
Array.Sort(a);
int count = 1;
int answer = 0;
// Traversing through the
// elements
for (int i = 1; i < n; i++)
{
if (a[i] == a[i - 1])
{
// Counting frequency of each
// elements
count += 1;
}
else
{
// Adding the contribution of
// the frequency to the answer
answer = answer + (count * (count - 1)) / 2;
count = 1;
}
}
answer = answer + (count * (count - 1)) / 2;
return answer;
}
// Driver Code
public static void Main ()
{
int []a = { 1, 2, 1, 2, 4 };
int n = a.Length;
// Print the count
Console.WriteLine(calculate(a, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find number
// of pairs in an array such
// that their XOR is 0
// Function to calculate
// the count
function calculate($a, $n)
{
// Sorting the list using
// built in function
sort($a);
$count = 1;
$answer = 0;
// Traversing through the
// elements
for ($i = 1; $i < $n; $i++)
{
if ($a[$i] == $a[$i - 1])
{
// Counting frequency of
// each elements
$count += 1;
}
else
{
// Adding the contribution of
// the frequency to the answer
$answer = $answer + ($count *
($count - 1)) / 2;
$count = 1;
}
}
$answer = $answer + ($count *
($count - 1)) / 2;
return $answer;
}
// Driver Code
$a = array(1, 2, 1, 2, 4);
$n = count($a);
// Print the count
echo calculate($a, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find number
// of pairs in an array such
// that their XOR is 0
// Function to calculate the
// count
function calculate(a, n)
{
// Sorting the list using
// built in function
a.sort();
let count = 1;
let answer = 0;
// Traversing through the
// elements
for (let i = 1; i < n; i++) {
if (a[i] == a[i - 1]){
// Counting frequency of each
// elements
count += 1;
}
else
{
// Adding the contribution of
// the frequency to the answer
answer = answer + Math.floor((count * (count - 1)) / 2);
count = 1;
}
}
answer = answer + Math.floor((count * (count - 1)) / 2);
return answer;
}
// Driver Code
let a = [ 1, 2, 1, 2, 4 ];
let n = a.length;
// Print the count
document.write(calculate(a, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción :
2
Complejidad de tiempo : O (N Log N)
Espacio Auxiliar: O(1), ya que no se utiliza espacio extra
Segundo enfoque : la solución Hashing (mapeo de índice)
es útil, si podemos contar la frecuencia de cada elemento en la array. La técnica de mapeo de índices se puede utilizar para contar la frecuencia de cada elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of pairs
// in an array such that their XOR is 0
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the answer
int calculate(int a[], int n){
// Finding the maximum of the array
int *maximum = max_element(a, a + n);
// Creating frequency array
// With initial value 0
int frequency[*maximum + 1] = {0};
// Traversing through the array
for(int i = 0; i < n; i++)
{
// Counting frequency
frequency[a[i]] += 1;
}
int answer = 0;
// Traversing through the frequency array
for(int i = 0; i < (*maximum)+1; i++)
{
// Calculating answer
answer = answer + frequency[i] * (frequency[i] - 1) ;
}
return answer/2;
}
// Driver Code
int main()
{
int a[] = {1, 2, 1, 2, 4};
int n = sizeof(a) / sizeof(a[0]);
// Function calling
cout << (calculate(a,n));
}
// This code is contributed by Smitha
Java
// Java program to find number of pairs
// in an array such that their XOR is 0
import java.util.*;
class GFG
{
// Function to calculate the answer
static int calculate(int a[], int n)
{
// Finding the maximum of the array
int maximum = Arrays.stream(a).max().getAsInt();
// Creating frequency array
// With initial value 0
int frequency[] = new int[maximum + 1];
// Traversing through the array
for (int i = 0; i < n; i++)
{
// Counting frequency
frequency[a[i]] += 1;
}
int answer = 0;
// Traversing through the frequency array
for (int i = 0; i < (maximum) + 1; i++)
{
// Calculating answer
answer = answer + frequency[i] * (frequency[i] - 1);
}
return answer / 2;
}
// Driver Code
public static void main(String[] args)
{
int a[] = {1, 2, 1, 2, 4};
int n = a.length;
// Function calling
System.out.println(calculate(a, n));
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python3 program to find number of pairs # in an array such that their XOR is 0 # Function to calculate the answer def calculate(a) : # Finding the maximum of the array maximum = max(a) # Creating frequency array # With initial value 0 frequency = [0 for x in range(maximum + 1)] # Traversing through the array for i in a : # Counting frequency frequency[i] += 1 answer = 0 # Traversing through the frequency array for i in frequency : # Calculating answer answer = answer + i * (i - 1) // 2 return answer # Driver Code a = [1, 2, 1, 2, 4] print(calculate(a))
C#
// C# program to find number of pairs
// in an array such that their XOR is 0
using System;
using System.Linq;
class GFG
{
// Function to calculate the answer
static int calculate(int []a, int n)
{
// Finding the maximum of the array
int maximum = a.Max();
// Creating frequency array
// With initial value 0
int []frequency = new int[maximum + 1];
// Traversing through the array
for (int i = 0; i < n; i++)
{
// Counting frequency
frequency[a[i]] += 1;
}
int answer = 0;
// Traversing through the frequency array
for (int i = 0; i < (maximum) + 1; i++)
{
// Calculating answer
answer = answer + frequency[i] *
(frequency[i] - 1);
}
return answer / 2;
}
// Driver Code
public static void Main(String[] args)
{
int []a = {1, 2, 1, 2, 4};
int n = a.Length;
// Function calling
Console.WriteLine(calculate(a, n));
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP program to find number
// of pairs in an array such
// that their XOR is 0
// Function to calculate the answer
function calculate($a, $n)
{
// Finding the maximum of the array
$maximum = max($a);
// Creating frequency array
// With initial value 0
$frequency = array_fill(0, $maximum + 1, 0);
// Traversing through the array
for($i = 0; $i < $n; $i++)
{
// Counting frequency
$frequency[$a[$i]] += 1;
}
$answer = 0;
// Traversing through
// the frequency array
for($i = 0; $i < ($maximum) + 1; $i++)
{
// Calculating answer
$answer = $answer + $frequency[$i] *
($frequency[$i] - 1);
}
return $answer / 2;
}
// Driver Code
$a = array(1, 2, 1, 2, 4);
$n = count($a);
// Function calling
echo (calculate($a,$n));
// This code is contributed by Smitha
?>
Javascript
<script>
// Javascript program to find number of pairs
// in an array such that their XOR is 0
// Function to calculate the answer
function calculate(a, n){
// Finding the maximum of the array
let maximum = Math.max(...a);
// Creating frequency array
// With initial value 0
let frequency = new Array(maximum + 1).fill(0);
// Traversing through the array
for(let i = 0; i < n; i++)
{
// Counting frequency
frequency[a[i]] += 1;
}
let answer = 0;
// Traversing through the frequency array
for(let i = 0; i < maximum+1; i++)
{
// Calculating answer
answer = answer + frequency[i] * (frequency[i] - 1) ;
}
return parseInt(answer/2);
}
// Driver Code
let a = [1, 2, 1, 2, 4];
let n = a.length;
// Function calling
document.write(calculate(a,n));
</script>
Producción :
2
Complejidad temporal : O(N)
Espacio auxiliar: O(N),
Nota: el método de asignación de índices solo se puede usar cuando los números en la array no son grandes. En tales casos, se puede utilizar el método de clasificación.