Считайте пары с помощью побитового XOR как ЧЕТНОЕ число

Опубликовано: 5 Января, 2022

Для массива из N целых чисел задача состоит в том, чтобы найти количество пар (i, j) таких, что A [i] ^ A [j] четно.
Примеры:

 Ввод: A [] = {5, 4, 7, 2, 1}
Выход: 4
Поскольку пара 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
Всего четных пар XOR = 4

Ввод: A [] = {7, 2, 8, 1, 0, 5, 11}
Выход: 9
Поскольку пара 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

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход - проверить каждую пару и вывести количество четных пар.
Ниже представлена реализация описанного выше подхода:

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;
}

Джава

// 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 prnumber 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>
Выход:
 4

Сложность времени: O (n ^ 2)
Эффективным решением является подсчет пар с помощью побитового XOR как нечетного числа, то есть oddEvenpairs. Затем верните totalPairs - oddEvenPairs, где totalPairs = (N * (N-1) / 2) и oddEvenPairs = count * (N - count) . Поскольку пары, которые дадут четное побитовое исключающее ИЛИ, следующие:

Even, Even 
Odd, Odd

Итак, найдите количество пар как с нечетными, так и с четными элементами и вычтите из общего числа. пар.
Ниже представлена реализация описанного выше подхода:

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;
}

Джава

// 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 pr 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 ) . " " ;
// 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>
Выход:
 4

Сложность времени: O (n)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023