Given an array of N integers. The task is to find the number of pairs (i, j) such that A[i] & A[j] is odd.
Examples:
Input: N = 4
A[] = { 5, 1, 3, 2 }
Output: 3
Since pair of A[] = ( 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 odd pair A( i, j ) = 3
Input : N = 6
A[] = { 5, 9, 0, 6, 7, 3 }
Output :6
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
A naive approach is to check for every pair and print the count of pairs.
Below is the implementation of the above approach:
C++
// C++ program to count pairs// with AND giving a odd number#include <iostream>using namespace std;// Function to count number of odd pairsint findOddPair(int A[], int N){ int i, j; // variable for counting odd pairs int oddPair = 0; // find all pairs for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { // find AND operation // check odd or even if ((A[i] & A[j]) % 2 != 0) oddPair++; } } // return number of odd pair return oddPair;}// Driver Codeint main(){ int a[] = { 5, 1, 3, 2 }; int n = sizeof(a) / sizeof(a[0]); // calling function findOddPair // and print number of odd pair cout << findOddPair(a, n) << endl; return 0;} |
Java
// Java program to count pairs// with AND giving a odd numberclass solution_1{ // Function to count// number of odd pairsstatic int findOddPair(int A[], int N){ int i, j; // variable for counting // odd pairs int oddPair = 0; // find all pairs for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { // find AND operation // check odd or even if ((A[i] & A[j]) % 2 != 0) oddPair++; } } // return number // of odd pair return oddPair;}// Driver Codepublic static void main(String args[]){ int a[] = { 5, 1, 3, 2 }; int n = a.length; // calling function findOddPair // and print number of odd pair System.out.println(findOddPair(a, n));}}// This code is contributed // by Arnab Kundu |
Python
# Python program to count pairs# with AND giving a odd number# Function to count number# of odd pairsdef findOddPair(A, N): # variable for counting odd pairs oddPair = 0 # find all pairs for i in range(0, N - 1): for j in range(i + 1, N - 1): # find AND operation # check odd or even if ((A[i] & A[j]) % 2 != 0): oddPair = oddPair + 1 # return number of odd pair return oddPair# Driver Codea = [5, 1, 3, 2]n = len(a) # calling function findOddPair# and print number of odd pairprint(findOddPair(a, n))# This code is contributed# by Shivi_Aggarwal |
C#
// C# program to count pairs// with AND giving a odd numberusing System;class GFG{ // Function to count// number of odd pairsstatic int findOddPair(int []A, int N){ int i, j; // variable for counting // odd pairs int oddPair = 0; // find all pairs for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { // find AND operation // check odd or even if ((A[i] & A[j]) % 2 != 0) oddPair++; } } // return number // of odd pair return oddPair;}// Driver Codepublic static void Main(){ int []a = { 5, 1, 3, 2 }; int n = a.Length; // calling function findOddPair // and print number of odd pair Console.WriteLine(findOddPair(a, n));}}// This code is contributed // inder_verma. |
PHP
<?php// PHP program to count pairs// with AND giving a odd number// Function to count // number of odd pairsfunction findOddPair(&$A, $N){ // variable for counting // odd pairs $oddPair = 0; // find all pairs for ($i = 0; $i < $N; $i++) { for ($j = $i + 1; $j < $N; $j++) { // find AND operation // check odd or even if (($A[$i] & $A[$j]) % 2 != 0) $oddPair = $oddPair + 1; } } // return number of odd pair return $oddPair;}// Driver Code$a = array(5, 1, 3, 2);$n = sizeof($a);// calling function findOddPair// and print number of odd pairecho(findOddPair($a, $n)); // This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script>// Javascript program to count pairs// with AND giving a odd number// Function to count// number of odd pairsfunction findOddPair(A, N){ var i, j; // variable for counting // odd pairs var oddPair = 0; // find all pairs for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { // find AND operation // check odd or even if ((A[i] & A[j]) % 2 != 0) oddPair++; } } // return number // of odd pair return oddPair;}// Driver Codevar a = [ 5, 1, 3, 2 ];var n = a.length;// calling function findOddPair// and print number of odd pairdocument.write(findOddPair(a, n));// This code is contributed by Amit Katiyar </script> |
Output:
3
Time Complexity:O(N^2)
Auxiliary Space: O(1)
An efficient solution is to count the odd numbers. Then return count * (count – 1)/2 because AND of two numbers can be odd only if only if a pair of both numbers are odd.
C++
// C++ program to count pairs with Odd AND#include <iostream>using namespace std;int findOddPair(int A[], int N){ // Count total odd numbers in int count = 0; for (int i = 0; i < N; i++) if ((A[i] % 2 == 1)) count++; // return count of even pair return count * (count - 1) / 2;}// Driver mainint main(){ int a[] = { 5, 1, 3, 2 }; int n = sizeof(a) / sizeof(a[0]); // calling function findOddPair // and print number of odd pair cout << findOddPair(a, n) << endl; return 0;} |
Java
// Java program to count // pairs with Odd ANDclass solution_1{ static int findOddPair(int A[], int N){ // Count total odd numbers in int count = 0; for (int i = 0; i < N; i++) if ((A[i] % 2 == 1)) count++; // return count of even pair return count * (count - 1) / 2;}// Driver Codepublic static void main(String args[]){ int a[] = { 5, 1, 3, 2 }; int n = a.length; // calling function findOddPair // and print number of odd pair System.out.println(findOddPair(a, n));}}// This code is contributed// by Arnab Kundu |
Python
# Python program to count # pairs with Odd AND def findOddPair(A, N): # Count total odd numbers count = 0; for i in range(0, N - 1): if ((A[i] % 2 == 1)): count = count+1 # return count of even pair return count * (count - 1) / 2# Driver Code a = [5, 1, 3, 2] n = len(a) # calling function findOddPair # and print number of odd pair print(int(findOddPair(a, n))) # This code is contributed# by Shivi_Aggarwal |
C#
// C# program to count // pairs with Odd AND using System;class GFG{public static int findOddPair(int[] A, int N){ // Count total odd numbers in int count = 0; for (int i = 0; i < N; i++) { if ((A[i] % 2 == 1)) { count++; } } // return count of even pair return count * (count - 1) / 2;}// Driver Code public static void Main(string[] args){ int[] a = new int[] {5, 1, 3, 2}; int n = a.Length; // calling function findOddPair // and print number of odd pair Console.WriteLine(findOddPair(a, n));}}// This code is contributed // by Shrikant13 |
PHP
<?php// PHP program to count // pairs with Odd AND function findOddPair(&$A, $N) { // Count total odd numbers $count = 0; for ($i = 0; $i < $N; $i++) if (($A[$i] % 2 == 1)) $count++; // return count of even pair return $count * ($count - 1) / 2; } // Driver Code $a = array(5, 1, 3, 2 ); $n = sizeof($a); // calling function findOddPair // and print number of odd pair echo(findOddPair($a, $n)); // This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script>// JavaScript program to count pairs with Odd ANDfunction findOddPair( A, N){ // Count total odd numbers in let count = 0; for (let i = 0; i < N; i++) if ((A[i] % 2 == 1)) count++; // return count of even pair return count * (count - 1) / 2;}// Driver main let a = [ 5, 1, 3, 2 ]; let n = a.length; // calling function findOddPair // and print number of odd pair document.write(findOddPair(a, n)); // This code contributed by aashish1995 </script> |
Output:
3
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!