Dada una array de N enteros, la tarea es encontrar el número de pares (i, j) tales que A[i] ^ A[j] sea par.
Ejemplos:
Input: A[] = { 5, 4, 7, 2, 1}
Output: 4
Since pair of A[] =
( 5, 4 ) = 1( 5, 7 ) = 2( 5, 2 ) = 7( 5, 1 ) = 4
( 4, 7 ) = 3( 4, 2 ) = 6( 4, 1 ) = 5
( 7, 2 ) = 5( 7, 1 ) = 6
( 2, 1 ) = 3
Total XOR even pair = 4
Input: A[] = { 7, 2, 8, 1, 0, 5, 11 }
Output: 9
Since pair of A[] =
( 7, 2 ) = 5( 7, 8 ) = 15( 7, 1 ) = 6( 7, 0 ) = 7( 7, 5 ) = 2( 7, 11 ) = 12
( 2, 8 ) = 10( 2, 1 ) = 3( 2, 0 ) = 2( 2, 5 ) = 7( 2, 11 ) = 9
( 8, 1 ) = 9( 8, 0 ) = 8( 8, 5 ) = 13( 8, 11 ) = 3
( 1, 0 ) = 1( 1, 5 ) = 4( 1, 11 ) = 10
( 0, 5 ) = 5( 0, 11 ) = 11
( 5, 11 ) = 14
Un enfoque ingenuo es verificar cada par e imprimir el conteo de pares que son pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count pairs
// with XOR giving a even number
#include <iostream>
using namespace std;
// Function to count number of even pairs
int findevenPair(int A[], int N)
{
int i, j;
// variable for counting even pairs
int evenPair = 0;
// find all pairs
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
// find XOR operation
// check even or even
if ((A[i] ^ A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
int main()
{
int A[] = { 5, 4, 7, 2, 1 };
int N = sizeof(A) / sizeof(A[0]);
// calling function findevenPair
// and print number of even pair
cout << findevenPair(A, N) << endl;
return 0;
}
C
// C program to count pairs
// with XOR giving a even number
#include <stdio.h>
// Function to count number of even pairs
int findevenPair(int A[], int N)
{
int i, j;
// variable for counting even pairs
int evenPair = 0;
// find all pairs
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
// find XOR operation
// check even or even
if ((A[i] ^ A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
int main()
{
int A[] = { 5, 4, 7, 2, 1 };
int N = sizeof(A) / sizeof(A[0]);
// calling function findevenPair
// and print number of even pair
printf("%d\n",findevenPair(A, N));
return 0;
}
// This code is contributed by kothvvsaakash.
Java
// Java program to count pairs
// with XOR giving a even number
import java.io.*;
class GFG
{
// Function to count number of even pairs
static int findevenPair(int []A, int N)
{
int i, j;
// variable for counting even pairs
int evenPair = 0;
// find all pairs
for (i = 0; i < N; i++)
{
for (j = i + 1; j < N; j++)
{
// find XOR operation
// check even or even
if ((A[i] ^ A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
public static void main (String[] args)
{
int A[] = { 5, 4, 7, 2, 1 };
int N = A.length;
// calling function findevenPair
// and print number of even pair
System.out.println(findevenPair(A, N));
}
}
// This code is contributed by inder_verma..
Python3
# Python3 program to count pairs # with XOR giving a even number # Function to count number of even pairs def findevenPair(A, N): # variable for counting even pairs evenPair = 0 # find all pairs for i in range(0, N): for j in range(i+1, N): # find XOR operation # check even or even if ((A[i] ^ A[j]) % 2 == 0): evenPair+=1 # return number of even pair return evenPair; # Driver Code def main(): A = [ 5, 4, 7, 2, 1 ] N = len(A) # calling function findevenPair # and print number of even pair print(findevenPair(A, N)) if __name__ == '__main__': main() # This code is contributed by PrinciRaj1992
C#
// C# program to count pairs
// with XOR giving a even number
using System;
class GFG
{
// Function to count number of
// even pairs
static int findevenPair(int []A, int N)
{
int i, j;
// variable for counting even pairs
int evenPair = 0;
// find all pairs
for (i = 0; i < N; i++)
{
for (j = i + 1; j < N; j++)
{
// find XOR operation
// check even or even
if ((A[i] ^ A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
public static void Main ()
{
int []A = { 5, 4, 7, 2, 1 };
int N = A.Length;
// calling function findevenPair
// and print number of even pair
Console.WriteLine(findevenPair(A, N));
}
}
// This code is contributed
// by inder_verma..
PHP
<?php
// PHP program to count pairs
// with XOR giving a even number
// Function to count number
// of even pairs
function findevenPair(&$A, $N)
{
// variable for counting even pairs
$evenPair = 0;
// find all pairs
for ($i = 0; $i < $N; $i++)
{
for ($j = $i + 1; $j < $N; $j++)
{
// find XOR operation
// check even or even
if (($A[$i] ^ $A[$j]) % 2 == 0)
$evenPair++;
}
}
// return number of even pair
return $evenPair;
}
// Driver Code
$A = array(5, 4, 7, 2, 1 );
$N = sizeof($A);
// calling function findevenPair
// and print number of even pair
echo (findevenPair($A, $N));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript program to count pairs
// with XOR giving a even number
// Function to count number of even pairs
function findevenPair(A, N)
{
let i, j;
// variable for counting even pairs
let evenPair = 0;
// find all pairs
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
// find XOR operation
// check even or even
if ((A[i] ^ A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
let A = [ 5, 4, 7, 2, 1 ];
let N = A.length;
// calling function findevenPair
// and print number of even pair
document.write(findevenPair(A, N));
// This code is contributed by souravmahato348.
</script>
Producción:
4
Complejidad de tiempo: O (n ^ 2)
Una solución eficiente es Contar pares con Bitwise XOR como número impar, es decir , pares pares impares . Luego devuelva pares totales – pares pares impares donde pares totales = (N * (N-1) / 2) y pares pares impares = recuento * (N – recuento) . Como, los pares que darán Even Bitwise XOR son:
par, par
impar, impar
Por lo tanto, encuentre la cantidad de pares con elementos pares e impares y reste del número total. de pares
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count pairs
// with XOR giving a even number
#include <iostream>
using namespace std;
// Function to count number of even pairs
int findEvenPair(int A[], int N)
{
int count = 0;
// find all pairs
for (int i = 0; i < N; i++) {
if (A[i] % 2 != 0)
count++;
}
int totalPairs = (N * (N - 1) / 2);
int oddEvenPairs = count * (N - count);
// return number of even pair
return totalPairs - oddEvenPairs;
}
// Driver Code
int main()
{
int a[] = { 5, 4, 7, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
// calling function findEvenPair
// and print number of even pair
cout << findEvenPair(a, n) << endl;
return 0;
}
C
// C program to count pairs
// with XOR giving a even number
#include <stdio.h>
// Function to count number of even pairs
int findEvenPair(int A[], int N)
{
int count = 0;
// find all pairs
for (int i = 0; i < N; i++) {
if (A[i] % 2 != 0)
count++;
}
int totalPairs = (N * (N - 1) / 2);
int oddEvenPairs = count * (N - count);
// return number of even pair
return totalPairs - oddEvenPairs;
}
// Driver Code
int main()
{
int a[] = { 5, 4, 7, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
// calling function findEvenPair
// and print number of even pair
printf("%d\n",findEvenPair(a, n));
return 0;
}
// This code is contributed by kothvvsaakash.
Java
// Java program to count pairs
// with XOR giving a even number
import java.io.*;
class GFG {
// Function to count number of even pairs
static int findEvenPair(int A[], int N)
{
int count = 0;
// find all pairs
for (int i = 0; i < N; i++) {
if (A[i] % 2 != 0)
count++;
}
int totalPairs = (N * (N - 1) / 2);
int oddEvenPairs = count * (N - count);
// return number of even pair
return totalPairs - oddEvenPairs;
}
// Driver Code
public static void main (String[] args) {
int a[] = { 5, 4, 7, 2, 1 };
int n = a.length;
// calling function findEvenPair
// and print number of even pair
System.out.println(findEvenPair(a, n));
}
//This code is contributed by akt_mit
}
Python3
# python program to count pairs # with XOR giving a even number # Function to count number of even pairs def findEvenPair(A, N): count = 0 # find all pairs for i in range(0,N): if (A[i] % 2 != 0): count+=1 totalPairs = (N * (N - 1) / 2) oddEvenPairs = count * (N - count) # return number of even pair return (int)(totalPairs - oddEvenPairs) # Driver Code def main(): a = [ 5, 4, 7, 2, 1 ] n = len(a) # calling function findEvenPair # and print number of even pair print(findEvenPair(a, n)) if __name__ == '__main__': main() # This code is contributed by 29AjayKumar
C#
// C# program to count pairs
// with XOR giving a even number
using System;
public class GFG {
// Function to count number of even pairs
static int findEvenPair(int []A, int N)
{
int count = 0;
// find all pairs
for (int i = 0; i < N; i++) {
if (A[i] % 2 != 0)
count++;
}
int totalPairs = (N * (N - 1) / 2);
int oddEvenPairs = count * (N - count);
// return number of even pair
return totalPairs - oddEvenPairs;
}
// Driver Code
public static void Main() {
int []a = { 5, 4, 7, 2, 1 };
int n = a.Length;
// calling function findEvenPair
// and print number of even pair
Console.Write(findEvenPair(a, n));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to count pairs
// with XOR giving a even number
// Function to count number of even pairs
function findEvenPair($A, $N)
{
$count = 0;
// find all pairs
for ($i = 0; $i < $N; $i++)
{
if ($A[$i] % 2 != 0)
$count++;
}
$totalPairs = ($N * ($N - 1) / 2);
$oddEvenPairs = $count * ($N - $count);
// return number of even pair
return $totalPairs - $oddEvenPairs;
}
// Driver Code
$a = array(5, 4, 7, 2, 1);
$n = sizeof($a);
// calling function findEvenPair
// and print number of even pair
echo findEvenPair($a, $n) . "\n";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to count pairs
// with XOR giving a even number
// Function to count number of even pairs
function findEvenPair(A, N)
{
let count = 0;
// find all pairs
for (let i = 0; i < N; i++) {
if (A[i] % 2 != 0)
count++;
}
let totalPairs = parseInt(N * (N - 1) / 2);
let oddEvenPairs = count * (N - count);
// return number of even pair
return totalPairs - oddEvenPairs;
}
// Driver Code
let a = [ 5, 4, 7, 2, 1 ];
let n = a.length;
// calling function findEvenPair
// and print number of even pair
document.write(findEvenPair(a, n));
</script>
Producción:
4
Complejidad de tiempo : O(n)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA