Dada una array de 
enteros. La tarea es encontrar el número de pares (i, j) tales que A[i] & A[j] sean pares.
Ejemplos :
Input: N = 4, A[] = { 5, 1, 3, 2 }
Output: 3
Since pair of A[] are:
( 5, 1 ), ( 5, 3 ), ( 5, 2 ), ( 1, 3 ), ( 1, 2 ), ( 3, 2 )
5 AND 1 = 1, 5 AND 3 = 1, 5 AND 2 = 0,
1 AND 3 = 1, 1 AND 2 = 0,
3 AND 2 = 2
Total even pair A( i, j ) = 3
Input : N = 6, A[] = { 5, 9, 0, 6, 7, 3 }
Output : 9
Since pair of A[] =
( 5, 9 ) = 1, ( 5, 0 ) = 0, ( 5, 6 ) = 4, ( 5, 7 ) = 5, ( 5, 3 ) = 1,
( 9, 0 ) = 0, ( 9, 6 ) = 0, ( 9, 7 ) = 1, ( 9, 3 ) = 1,
( 0, 6 ) = 0, ( 0, 7 ) = 0, ( 0, 3 ) = 0,
( 6, 7 ) = 6, ( 6, 3 ) = 2,
( 7, 3 ) = 3
Un enfoque ingenuo es comprobar cada par e imprimir el recuento de pares que son pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count pair with
// bitwise-AND as even number
#include <iostream>
using namespace std;
// Function to count number of pairs EVEN bitwise AND
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 AND operation
// to check evenpair
if ((A[i] & A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
int main()
{
int a[] = { 5, 1, 3, 2 };
int n = sizeof(a) / sizeof(a[0]);
cout << findevenPair(a, n) << endl;
return 0;
}
C
// C program to count pair with
// bitwise-AND as even number
#include <stdio.h>
// Function to count number of pairs EVEN bitwise AND
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 AND operation
// to check evenpair
if ((A[i] & A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
int main()
{
int a[] = { 5, 1, 3, 2 };
int n = sizeof(a) / sizeof(a[0]);
printf("%d\n",findevenPair(a, n));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to count pair with
// bitwise-AND as even number
import java.io.*;
class GFG
{
// Function to count number of
// pairs EVEN bitwise AND
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 AND operation
// to check evenpair
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, 1, 3, 2 };
int n = a.length;
System.out.println(findevenPair(a, n));
}
}
// This code is contributed by anuj_67..
Python3
# Python 3 program to count pair with # bitwise-AND as even number # Function to count number of # pairs EVEN bitwise AND 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 AND operation to # check evenpair if ((A[i] & A[j]) % 2 == 0): evenPair += 1 # return number of even pair return evenPair # Driver Code a = [ 5, 1, 3, 2 ] n = len(a) print(findevenPair(a, n)) # This code is contributed # by PrinciRaj1992
C#
// C# program to count pair with
// bitwise-AND as even number
using System;
class GFG
{
// Function to count number of
// pairs EVEN bitwise AND
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 AND operation
// to check evenpair
if ((A[i] & A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
public static void Main ()
{
int []a = { 5, 1, 3, 2 };
int n = a.Length;
Console.WriteLine(findevenPair(a, n));
}
}
// This code is contributed by anuj_67..
PHP
<?php
// PHP program to count pair with
// bitwise-AND as even number
// Function to count number of
// pairs EVEN bitwise AND
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 AND operation
// to check evenpair
if (($A[$i] & $A[$j]) % 2 == 0)
$evenPair++;
}
}
// return number of even pair
return $evenPair;
}
// Driver Code
$a = array(5, 1, 3, 2 );
$n = sizeof($a);
echo findevenPair($a, $n);
// This code is contributed by akt_mit
?>
Javascript
<script>
// Javascript program to count pair with
// bitwise-AND as even number
// Function to count number of pairs EVEN bitwise AND
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 AND operation
// to check evenpair
if ((A[i] & A[j]) % 2 == 0)
evenPair++;
}
}
// return number of even pair
return evenPair;
}
// Driver Code
let a = [ 5, 1, 3, 2 ];
let n = a.length;
document.write(findevenPair(a, n));
// This code is contributed by souravmahato348.
</script>
Producción:
3
Un enfoque eficiente será observar que el AND bit a bit de dos números será par si al menos uno de los dos números es par. Entonces, cuente todos los números impares en la array, digamos count . Ahora, el número de pares con ambos elementos impares será count*(count-1)/2 .
Por lo tanto, el número de elementos con al menos un elemento par será:
Total Pairs - Count of pair with both odd elements
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count pair with
// bitwise-AND as even number
#include <iostream>
using namespace std;
// Function to count number of pairs
// with EVEN bitwise AND
int findevenPair(int A[], int N)
{
int count = 0;
// count odd numbers
for (int i = 0; i < N; i++)
if (A[i] % 2 != 0)
count++;
// count odd pairs
int oddCount = count * (count - 1) / 2;
// return number of even pair
return (N * (N - 1) / 2) - oddCount;
}
// Driver Code
int main()
{
int a[] = { 5, 1, 3, 2 };
int n = sizeof(a) / sizeof(a[0]);
cout << findevenPair(a, n) << endl;
return 0;
}
C
// C program to count pair with
// bitwise-AND as even number
#include <stdio.h>
// Function to count number of pairs
// with EVEN bitwise AND
int findevenPair(int A[], int N)
{
int count = 0;
// count odd numbers
for (int i = 0; i < N; i++)
if (A[i] % 2 != 0)
count++;
// count odd pairs
int oddCount = count * (count - 1) / 2;
// return number of even pair
return (N * (N - 1) / 2) - oddCount;
}
// Driver Code
int main()
{
int a[] = { 5, 1, 3, 2 };
int n = sizeof(a) / sizeof(a[0]);
printf("%d\n",findevenPair(a, n));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to count pair with
// bitwise-AND as even number
import java.io.*;
class GFG {
// Function to count number of pairs
// with EVEN bitwise AND
static int findevenPair(int A[], int N)
{
int count = 0;
// count odd numbers
for (int i = 0; i < N; i++)
if (A[i] % 2 != 0)
count++;
// count odd pairs
int oddCount = count * (count - 1) / 2;
// return number of even pair
return (N * (N - 1) / 2) - oddCount;
}
// Driver Code
public static void main (String[] args) {
int a[] = { 5, 1, 3, 2 };
int n =a.length;
System.out.print( findevenPair(a, n));
}
}
// This code is contributed by anuj_67..
Python3
# Python 3 program to count pair with # bitwise-AND as even number # Function to count number of pairs # with EVEN bitwise AND def findevenPair(A, N): count = 0 # count odd numbers for i in range(0, N): if (A[i] % 2 != 0): count += 1 # count odd pairs oddCount = count * (count - 1) / 2 # return number of even pair return (int)((N * (N - 1) / 2) - oddCount) # Driver Code a = [5, 1, 3, 2 ] n = len(a) print(findevenPair(a, n)) # This code is contributed # by PrinciRaj1992
C#
// C# program to count pair with
// bitwise-AND as even number
using System;
public class GFG{
// Function to count number of pairs
// with EVEN bitwise AND
static int findevenPair(int []A, int N)
{
int count = 0;
// count odd numbers
for (int i = 0; i < N; i++)
if (A[i] % 2 != 0)
count++;
// count odd pairs
int oddCount = count * (count - 1) / 2;
// return number of even pair
return (N * (N - 1) / 2) - oddCount;
}
// Driver Code
static public void Main (){
int []a = { 5, 1, 3, 2 };
int n =a.Length;
Console.WriteLine( findevenPair(a, n));
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program to count pair with
// bitwise-AND as even number
// Function to count number of pairs
// with EVEN bitwise AND
function findevenPair($A, $N)
{
$count = 0;
// count odd numbers
for ($i = 0; $i < $N; $i++)
if ($A[$i] % 2 != 0)
$count++;
// count odd pairs
$oddCount = $count * ($count - 1) / 2;
// return number of even pair
return ($N * ($N - 1) / 2) - $oddCount;
}
// Driver Code
$a = array(5, 1, 3, 2);
$n = sizeof($a);
echo findevenPair($a, $n) . "\n";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to count pair with
// bitwise-AND as even number
// Function to count number of pairs
// with EVEN bitwise AND
function findevenPair(A, N)
{
let count = 0;
// Count odd numbers
for(let i = 0; i < N; i++)
if (A[i] % 2 != 0)
count++;
// Count odd pairs
let oddCount = parseInt((count *
(count - 1)) / 2);
// Return number of even pair
return parseInt((N * (N - 1)) / 2) - oddCount;
}
// Driver Code
let a = [ 5, 1, 3, 2 ];
let n = a.length;
document.write(findevenPair(a, n));
// This code is contributed by subhammahato348
</script>
Producción:
3
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