Dada una array A[] de tamaño N. La tarea es encontrar cuántos pares (i, j) existen de modo que A[i] O A[j] sea par.
Ejemplos:
Input : N = 4
A[] = { 5, 6, 2, 8 }
Output :3
Explanation :
Since pair of A[] = ( 5, 6 ), ( 5, 2 ), ( 5, 8 ),
( 6, 2 ), ( 6, 8 ), ( 2, 8 )
5 OR 6 = 7, 5 OR 2 = 7, 5 OR 8 = 13
6 OR 2 = 6, 6 OR 8 = 14, 2 OR 8 = 10
Total pair A( i, j ) = 6 and Even = 3
Input : N = 7
A[] = {8, 6, 2, 7, 3, 4, 9}
Output :6
Una solución simple es verificar cada par.
C++
// C++ program to count pairs with even OR
#include <iostream>
using namespace std;
int findEvenPair(int A[], int N)
{
int evenPair = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// find OR operation
// check odd or even
if ((A[i] | A[j]) % 2 == 0)
evenPair++;
}
}
// return count of even pair
return evenPair;
}
// Driver main
int main()
{
int A[] = { 5, 6, 2, 8 };
int N = sizeof(A) / sizeof(A[0]);
cout << findEvenPair(A, N) << endl;
return 0;
}
Java
// Java program to count
// pairs with even OR
import java.io.*;
class GFG
{
static int findEvenPair(int A[],
int N)
{
int evenPair = 0;
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// find OR operation
// check odd or even
if ((A[i] | A[j]) % 2 == 0)
evenPair++;
}
}
// return count of even pair
return evenPair;
}
// Driver Code
public static void main (String[] args)
{
int A[] = { 5, 6, 2, 8 };
int N = A.length;
System.out.println(findEvenPair(A, N));
}
}
// This code is contributed
// by inder_verma.
Python 3
# Python 3 program to count pairs # with even OR def findEvenPair(A, N) : evenPair = 0 for i in range(N) : for j in range(i+1, N): # find OR operation # check odd or even if (A[i] | A[j]) % 2 == 0 : evenPair += 1 # return count of even pair return evenPair # Driver Code if __name__ == "__main__" : A = [ 5, 6, 2, 8] N = len(A) # function calling print(findEvenPair(A, N)) # This code is contributed by ANKITRAI1
C#
// C# program to count
// pairs with even OR
using System;
class GFG
{
static int findEvenPair(int []A,
int N)
{
int evenPair = 0;
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// find OR operation
// check odd or even
if ((A[i] | A[j]) % 2 == 0)
evenPair++;
}
}
// return count of even pair
return evenPair;
}
// Driver Code
public static void Main ()
{
int []A = { 5, 6, 2, 8 };
int N = A.Length;
Console.WriteLine(findEvenPair(A, N));
}
}
// This code is contributed
// by inder_verma.
PHP
<?php
// PHP program to count
// pairs with even OR
function findEvenPair($A, $N)
{
$evenPair = 0;
for ($i = 0; $i < $N; $i++)
{
for ($j = $i + 1; $j < $N; $j++)
{
// find OR operation
// check odd or even
if (($A[$i] | $A[$j]) % 2 == 0)
$evenPair++;
}
}
// return count of even pair
return $evenPair;
}
// Driver Code
$A = array(5, 6, 2, 8);
$N = count($A);
echo findEvenPair($A, $N);
// This code is contributed
// by inder_verma.
?>
Javascript
<script>
// JavaScript program to count pairs with even OR
function findEvenPair(A, N)
{
let evenPair = 0;
for (let i = 0; i < N; i++) {
for (let j = i + 1; j < N; j++) {
// find OR operation
// check odd or even
if ((A[i] | A[j]) % 2 == 0)
evenPair++;
}
}
// return count of even pair
return evenPair;
}
// Driver main
let A = [5, 6, 2, 8 ];
let N = A.length;
document.write(findEvenPair(A, N));
// This code contributed by Rajput-Ji
</script>
Producción:
3
Complejidad de tiempo: O (N ^ 2)
Una solución eficiente es contar números con el último bit como 0. Luego devuelva el conteo * (contar – 1)/2. Tenga en cuenta que OR de dos números puede ser par solo si sus últimos bits son 0.
C++
// C++ program to count pairs with even OR
#include <iostream>
using namespace std;
int findEvenPair(int A[], int N)
{
// Count total even numbers in
// array.
int count = 0;
for (int i = 0; i < N; i++)
if (!(A[i] & 1))
count++;
// return count of even pair
return count * (count - 1) / 2;
}
// Driver main
int main()
{
int A[] = { 5, 6, 2, 8 };
int N = sizeof(A) / sizeof(A[0]);
cout << findEvenPair(A, N) << endl;
return 0;
}
Java
// Java program to count
// pairs with even OR
import java.io.*;
class GFG
{
static int findEvenPair(int A[], int N)
{
// Count total even numbers in
// array.
int count = 0;
for (int i = 0; i < N; i++)
if ((!((A[i] & 1) > 0)))
count++;
// return count of even pair
return count * (count - 1) / 2;
}
// Driver Code
public static void main (String[] args)
{
int A[] = { 5, 6, 2, 8 };
int N = A.length;
System.out.println(findEvenPair(A, N));
}
}
// This code is contributed
// by inder_verma.
Python 3
# Python 3 program to count # pairs with even OR def findEvenPair(A, N): # Count total even numbers # in array. count = 0 for i in range(N): if (not (A[i] & 1)): count += 1 # return count of even pair return count * (count - 1) // 2 # Driver Code if __name__ == "__main__": A = [ 5, 6, 2, 8 ] N = len(A) print(findEvenPair(A, N)) # This code is contributed # by ChitraNayal
C#
// C# program to count
// pairs with even OR
using System;
class GFG
{
static int findEvenPair(int []A, int N)
{
// Count total even numbers
// in array.
int count = 0;
for (int i = 0; i < N; i++)
if ((!((A[i] & 1) > 0)))
count++;
// return count of even pair
return count * (count - 1) / 2;
}
// Driver Code
public static void Main (String[] args)
{
int []A = { 5, 6, 2, 8 };
int N = A.Length;
Console.WriteLine(findEvenPair(A, N));
}
}
// This code is contributed
// by Kirti_Mangal
PHP
<?php
// PHP program to count pairs
// with even OR
function findEvenPair(&$A, $N)
{
// Count total even numbers in
// array.
$count = 0;
for ($i = 0; $i < $N; $i++)
if (!($A[$i] & 1))
$count++;
// return count of even pair
return $count * ($count - 1) / 2;
}
// Driver Code
$A = array(5, 6, 2, 8 );
$N = sizeof($A);
echo findEvenPair($A, $N)."\n";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to count
// pairs with even OR
function findEvenPair(A,N)
{
// Count total even numbers in
// array.
let count = 0;
for (let i = 0; i < N; i++)
if ((!((A[i] & 1) > 0)))
count++;
// return count of even pair
return count * (count - 1) / 2;
}
// Driver Code
let A=[5, 6, 2, 8 ];
let N = A.length;
document.write(findEvenPair(A, N));
// This code is contributed by rag2127
</script>
Producción:
3
Complejidad de tiempo: O(N)