Given an array of N integers, the task is to find the number of pairs (i, j) such that A[i] ^ A[j] is even.
Examples:
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
A naive approach is to check for every pair and print the count of pairs that are even.
Below is the implementation of the above approach:
C++
// C++ program to count pairs// with XOR giving a even number#include <iostream>using namespace std;// Function to count number of even pairsint 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 Codeint 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 pairsint 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 Codeint 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 numberimport java.io.*;class GFG{// Function to count number of even pairsstatic 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 Codepublic 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 pairsdef 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 Codedef 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 numberusing System;class GFG{// Function to count number of// even pairsstatic 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 Codepublic 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 pairsfunction 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 pairecho (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 pairsfunction 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 Codelet A = [ 5, 4, 7, 2, 1 ];let N = A.length;// calling function findevenPair// and print number of even pairdocument.write(findevenPair(A, N));// This code is contributed by souravmahato348.</script> |
Output
4
Time Complexity: O(n^2)
Auxiliary Space: O(1)
An efficient solution is to Count pairs with Bitwise XOR as ODD number i.e. oddEvenpairs. Then return totalPairs – oddEvenPairs where totalPairs = (N * (N-1) / 2) and oddEvenPairs = count * (N – count).
As, pairs that will give Even Bitwise XOR are :
Even, Even
Odd, Odd
So, find the count of pairs with both odd and even elements and subtract from total no. of pairs.
Below is the implementation of the above approach:
C++
// C++ program to count pairs// with XOR giving a even number#include <iostream>using namespace std;// Function to count number of even pairsint 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 Codeint 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 pairsint 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 Codeint 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 numberimport 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 pairsdef 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 Codedef 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 pairsfunction 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 pairecho 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 pairsfunction 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> |
Output
4
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/count-pairs-with-bitwise-xor-as-even-number/ […]