# Count pairs with odd Bitwise XOR that can be removed and replaced by their Bitwise OR

Given an array **arr[]** consisting of **N** integers, the task is to count the number of pairs whose Bitwise XOR is odd, that can be removed and replaced by their Bitwise OR values until no such pair exists in the array.

**Examples:**

Input:arr[] = {5, 4, 7, 2}Output:2Explanation:Pair (5, 4):Bitwise XOR of 5 and 4 is 1. Remove this pair and add their Bitwise OR (= 5) into the array. Therefore, the modified array is {5, 7, 2}.Pair (5, 2):Bitwise XOR of 5 and 2 is 7. Remove this pair and add their Bitwise OR (= 7) into the array. Therefore, the modified array is {7, 7}.Therefore, the count of such pairs that can be removed is 2.

Input:arr[] = {2, 4, 6}Output:0

**Approach:** The given problem can be solved based on the following observations:

- Bitwise XOR of a pair is
**odd**only if one element is**odd**and the other is**even**. - Therefore, removing such a pair from the array and adding their Bitwise OR into the array doesn’t affect the total count of odd elements in the array. But the count of even array elements reduces by
**1**.

Therefore, the idea is to find the count of even elements present in the given array. If the count of even elements is **N**, then **0** moves are required. Otherwise, print the value of **count** as the resultant count of pairs required to be removed.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count the number of pairs` `// required to be removed from the array` `// and replaced by their Bitwise OR values` `void` `countPairs(` `int` `arr[], ` `int` `N)` `{` ` ` `// Stores the count of` ` ` `// even array elements` ` ` `int` `even = 0;` ` ` `// Traverse the given array` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Increment the count` ` ` `// of even array elements` ` ` `if` `(arr[i] % 2 == 0)` ` ` `even++;` ` ` `}` ` ` `// If the array contains at` ` ` `// least one odd array element` ` ` `if` `(N - even >= 1) {` ` ` `cout << even;` ` ` `return` `;` ` ` `}` ` ` `// Otherwise, print 0` ` ` `cout << 0;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 5, 4, 7, 2 };` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `countPairs(arr, N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `import` `java.lang.*;` `import` `java.util.*;` `class` `GFG{` `// Function to count the number of pairs` `// required to be removed from the array` `// and replaced by their Bitwise OR values` `static` `void` `countPairs(` `int` `arr[], ` `int` `N)` `{` ` ` ` ` `// Stores the count of` ` ` `// even array elements` ` ` `int` `even = ` `0` `;` ` ` `// Traverse the given array` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++)` ` ` `{` ` ` ` ` `// Increment the count` ` ` `// of even array elements` ` ` `if` `(arr[i] % ` `2` `== ` `0` `)` ` ` `even++;` ` ` `}` ` ` `// If the array contains at` ` ` `// least one odd array element` ` ` `if` `(N - even >= ` `1` `)` ` ` `{` ` ` `System.out.println(even);` ` ` `return` `;` ` ` `}` ` ` `// Otherwise, print 0` ` ` `System.out.println(` `0` `);` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `arr[] = { ` `5` `, ` `4` `, ` `7` `, ` `2` `};` ` ` `int` `N = arr.length;` ` ` `countPairs(arr, N);` `}` `}` `// This code is contributed by Kingash` |

## Python3

`# Python3 program for the above approach` `# Function to count the number of pairs` `# required to be removed from the array` `# and replaced by their Bitwise OR values` `def` `countPairs(arr, N):` ` ` `# Stores the count of` ` ` `# even array elements` ` ` `even ` `=` `0` ` ` `# Traverse the given array` ` ` `for` `i ` `in` `range` `(N):` ` ` `# Increment the count` ` ` `# of even array elements` ` ` `if` `(arr[i] ` `%` `2` `=` `=` `0` `):` ` ` `even ` `+` `=` `1` ` ` ` ` `# If the array contains at` ` ` `# least one odd array element` ` ` `if` `(N ` `-` `even >` `=` `1` `):` ` ` `print` `(even)` ` ` `return` ` ` `# Otherwise, print 0` ` ` `print` `(` `0` `)` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `arr ` `=` `[ ` `5` `, ` `4` `, ` `7` `, ` `2` `]` ` ` `N ` `=` `len` `(arr)` ` ` ` ` `countPairs(arr, N)` `# This code is contributed by AnkThon` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` ` ` `// Function to count the number of pairs` `// required to be removed from the array` `// and replaced by their Bitwise OR values` `static` `void` `countPairs(` `int` `[] arr, ` `int` `N)` `{` ` ` ` ` `// Stores the count of` ` ` `// even array elements` ` ` `int` `even = 0;` ` ` `// Traverse the given array` ` ` `for` `(` `int` `i = 0; i < N; i++)` ` ` `{` ` ` ` ` `// Increment the count` ` ` `// of even array elements` ` ` `if` `(arr[i] % 2 == 0)` ` ` `even++;` ` ` `}` ` ` `// If the array contains at` ` ` `// least one odd array element` ` ` `if` `(N - even >= 1)` ` ` `{` ` ` `Console.WriteLine(even);` ` ` `return` `;` ` ` `}` ` ` `// Otherwise, print 0` ` ` `Console.WriteLine(0);` `}` `// Driver code` `static` `void` `Main()` `{` ` ` `int` `[] arr = { 5, 4, 7, 2 };` ` ` `int` `N = arr.Length;` ` ` `countPairs(arr, N);` `}` `}` `// This code is contributed by sanjoy_62` |

## Javascript

`<script>` `// JavaScript program for the above approach` `// Function to count the number of pairs` `// required to be removed from the array` `// and replaced by their Bitwise OR values` `function` `countPairs(arr, N)` `{` ` ` `// Stores the count of` ` ` `// even array elements` ` ` `let even = 0;` ` ` `// Traverse the given array` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `// Increment the count` ` ` `// of even array elements` ` ` `if` `(arr[i] % 2 == 0)` ` ` `even++;` ` ` `}` ` ` `// If the array contains at` ` ` `// least one odd array element` ` ` `if` `(N - even >= 1) {` ` ` `document.write(even);` ` ` `return` `;` ` ` `}` ` ` `// Otherwise, print 0` ` ` `document.write(0);` `}` `// Driver Code` `let arr = [ 5, 4, 7, 2 ];` `let N = arr.length;` `countPairs(arr, N);` `</script>` |

**Output:**

2

**Time Complexity:** O(N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.