Given an array A[] of size N. The task is to find how many pair(i, j) exists such that A[i] OR A[j] is odd.
Examples:
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 Odd = 3
Input : N = 7
A[] = {8, 6, 2, 7, 3, 4, 9}
Output :15
A Simple Solution is to check every pair and find the Bitwise-OR and count all such pairs with Bitwise OR as odd.
Below is the implementation of the above approach:
C++
// C++ program to count pairs with odd OR#include <iostream>using namespace std;// Function to count pairs with odd ORint findOddPair(int A[], int N){ int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair;}// Driver Codeint main(){ int A[] = { 5, 6, 2, 8 }; int N = sizeof(A) / sizeof(A[0]); cout << findOddPair(A, N) << endl; return 0;} |
C
// C program to count pairs with odd OR#include <stdio.h>// Function to count pairs with odd ORint findOddPair(int A[], int N){ int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair;}// Driver Codeint main(){ int A[] = { 5, 6, 2, 8 }; int N = sizeof(A) / sizeof(A[0]); printf("%d\n",findOddPair(A, N)); return 0;}// This code is contributed by kothavvsaakash. |
Java
// Java program to count pairs// with odd ORclass GFG{// Function to count pairs with odd ORstatic int findOddPair(int A[], int N){ int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair;}// Driver Codepublic static void main(String []args){ int A[] = { 5, 6, 2, 8 }; int N = A.length; System.out.println(findOddPair(A, N));}}// This code is contributed by ANKITRAI1 |
Python3
# Python3 program to count pairs with odd OR # Function to count pairs with odd ORdef findOddPair(A, N): oddPair = 0 for i in range(0, N): for j in range(i+1, N): # find OR operation # check odd or odd if ((A[i] | A[j]) % 2 != 0): oddPair+=1 # return count of odd pair return oddPair # Driver Codedef main(): A = [ 5, 6, 2, 8 ] N = len(A) print(findOddPair(A, N))if __name__ == '__main__': main()# This code is contributed by PrinciRaj1992 |
C#
// C# program to count pairs // with odd ORusing System;public class GFG{ // Function to count pairs with odd OR static int findOddPair(int[] A, int N) { int oddPair = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair; } // Driver Code static public void Main (){ int []A = { 5, 6, 2, 8 }; int N = A.Length; Console.WriteLine(findOddPair(A, N)); } } //This code is contributed by ajit |
PHP
<?php//PHP program to count pairs with odd OR// Function to count pairs with odd ORfunction findOddPair($A, $N){ $oddPair = 0; for ($i = 0; $i < $N; $i++) { for ($j = $i + 1; $j < $N; $j++) { // find OR operation // check odd or odd if (($A[$i] | $A[$j]) % 2 != 0) $oddPair++; } } // return count of odd pair return $oddPair;}// Driver Code $A = array (5, 6, 2, 8 ); $N = sizeof($A) / sizeof($A[0]); echo findOddPair($A, $N),"\n";#This code is contributed by ajit?> |
Javascript
<script>// Javascript program to count pairs with odd OR// Function to count pairs with odd ORfunction findOddPair(A, N){ let oddPair = 0; for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { // find OR operation // check odd or odd if ((A[i] | A[j]) % 2 != 0) oddPair++; } } // return count of odd pair return oddPair;}// Driver Codelet A = [ 5, 6, 2, 8 ];let N = A.length;document.write(findOddPair(A, N));// This code is contributed by souravmahato348.</script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
An Efficient Solution is to count pairs with even OR and subtract them with a total number of pairs to get pairs with odd Bitwise-OR. To do this, count numbers with last bit as 0. Then a number of pairs with even Bitwise-OR = count * (count – 1)/2 and total number of pairs will be N*(N-1)/2.
Therefore, pairs with ODD Bitwise-OR will be:
Total Pairs - Pairs with EVEN Bitwise-OR
Below is the implementation of the above approach:
C++
// C++ program to count pairs with odd OR#include <iostream>using namespace std;// Function to count pairs with odd ORint countOddPair(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++; // Even pair count int evenPairCount = count * (count - 1) / 2; // Total pairs int totPairs = N * (N - 1) / 2; // Return Odd pair count return totPairs - evenPairCount;}// Driver mainint main(){ int A[] = { 5, 6, 2, 8 }; int N = sizeof(A) / sizeof(A[0]); cout << countOddPair(A, N) << endl; return 0;} |
Java
// Java program to count pairs with odd ORpublic class GFG {// Function to count pairs with odd OR static int countOddPair(int A[], int N) { // Count total even numbers in // array int count = 0; for (int i = 0; i < N; i++) { if ((A[i] % 2 != 1)) { count++; } } // Even pair count int evenPairCount = count * (count - 1) / 2; // Total pairs int totPairs = N * (N - 1) / 2; // Return Odd pair count return totPairs - evenPairCount; }// Driver main public static void main(String[] args) { int A[] = {5, 6, 2, 8}; int N = A.length; System.out.println(countOddPair(A, N)); }} |
Python3
# Python 3program to count pairs with odd OR# Function to count pairs with odd ORdef countOddPair(A, N): # Count total even numbers in # array count = 0 for i in range(0, N): if (A[i] % 2 != 1): count+=1 # Even pair count evenPairCount = count * (count - 1) / 2 # Total pairs totPairs = N * (N - 1) / 2 # Return Odd pair count return (int)(totPairs - evenPairCount) # Driver CodeA = [ 5, 6, 2, 8 ]N = len(A)print(countOddPair(A, N))# This code is contributed by PrinciRaj1992 |
C#
// C# program to count pairs with odd ORusing System; public class GFG { // Function to count pairs with odd OR static int countOddPair(int []A, int N) { // Count total even numbers in // array int count = 0; for (int i = 0; i < N; i++) { if ((A[i] % 2 != 1)) { count++; } } // Even pair count int evenPairCount = count * (count - 1) / 2; // Total pairs int totPairs = N * (N - 1) / 2; // Return Odd pair count return totPairs - evenPairCount; } // Driver main public static void Main() { int []A = {5, 6, 2, 8}; int N = A.Length; Console.WriteLine(countOddPair(A, N)); }}/*This code is contributed by PrinciRaj1992*/ |
PHP
<?php// PHP program to count pairs with odd OR // Function to count pairs with odd OR function countOddPair( $A, $N) { // Count total even numbers // in array $count = 0; for ($i = 0; $i < $N; $i++) if (!($A[$i] & 1)) $count++; // Even pair count $evenPairCount = $count * ($count - 1) / 2; // Total pairs $totPairs = $N * ($N - 1) / 2; // Return Odd pair count return ($totPairs - $evenPairCount); } // Driver main $A = array( 5, 6, 2, 8 ); $N = sizeof($A); echo countOddPair($A, $N),"\n"; // This code is contributed by Sach_Code?> |
Javascript
<script>// Javascript program to count// pairs with odd OR// Function to count pairs with odd ORfunction countOddPair(A, N){ // Count total even numbers in // array let count = 0; for (let i = 0; i < N; i++) if (!(A[i] & 1)) count++; // Even pair count let evenPairCount = parseInt(count * (count - 1) / 2); // Total pairs let totPairs = parseInt(N * (N - 1) / 2); // Return Odd pair count return totPairs - evenPairCount;}// Driver main let A = [ 5, 6, 2, 8 ]; let N = A.length; document.write(countOddPair(A, N));</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!