Posted on by Kalkicode
Code Bit Logic

# Count pairs with Odd XOR occurrence

The problem requires counting the number of pairs from an array where the XOR (exclusive OR) of the elements in the pair results in an odd number. XOR is a bitwise operation that returns 1 if two bits are different, and 0 if they are the same. The task is to find all pairs such that the XOR of their elements is an odd number.

## Problem Statement

Given an array of integers, the goal is to count the number of pairs (i, j) where i < j, and the XOR of arr[i] and arr[j] is an odd number.

## Explanation with Example

Let's take the input array [1, 6, 3, 8, 3, 4, 2] as an example.

Pairs with odd XOR occurrence:

• (1 ⊕ 6) = 7 (Odd)
• (1 ⊕ 8) = 9 (Odd)
• (1 ⊕ 4) = 5 (Odd)
• (1 ⊕ 2) = 3 (Odd)
• (6 ⊕ 3) = 5 (Odd)
• (3 ⊕ 8) = 11 (Odd)
• (3 ⊕ 4) = 7 (Odd)
• (3 ⊕ 2) = 1 (Odd)
• (8 ⊕ 3) = 11 (Odd)
• (4 ⊕ 3) = 7 (Odd)
• (2 ⊕ 3) = 1 (Odd)

The total count of such pairs is 12.

## Pseudocode

``````// Function to count pairs with odd XOR occurrence
function countOddXorPair(arr[], n):
odd = 0
even = 0

// Counting Even and Odd occurrence in array
for i from 0 to n-1:
if (arr[i] % 2) == 0:
// When elements are even
increment even by 1
else:
// When elements are odd
increment odd by 1

// Display given array

// Calculate the result by multiplying odd and even
result = odd * even

// Display the result
print "Result:", result
``````
1. Initialize variables "odd" and "even" to 0.
2. Iterate through the array and check each element: a. If the element is even, increment "even" by 1. b. If the element is odd, increment "odd" by 1.
3. The result will be the product of "odd" and "even".

## Algorithm

1. Start
2. Define a function countOddXorPair(arr[], n):
3. Initialize variables odd = 0 and even = 0.
4. Iterate i from 0 to n-1: a. If (arr[i] % 2) == 0, increment even by 1. b. Else, increment odd by 1.
5. Print the given array elements using printData function.
6. Calculate the result by multiplying odd and even.
7. Print the result.
8. End

## Code Solution

Here given code implementation process.

``````// C program for
// Count pairs with Odd XOR occurrence
#include <stdio.h>

// Display array elements
void printData(int arr[], int n)
{
printf("\n Array : ");
for (int i = 0; i < n; ++i)
{
// print element
printf("  %d", arr[i]);
}
}
void countOddXorPair(int arr[], int n)
{
// Display given array
printData(arr, n);
int odd = 0;
int even = 0;
// Counting Even and Odd occurrence in array
for (int i = 0; i < n; ++i)
{
if ((arr[i] % 2) == 0)
{
// When elements are even
even++;
}
else
{
// When elements are odd
odd++;
}
}
printf("\n Result : %d ", odd *even);
}
int main(int argc, char
const *argv[])
{
int arr[] = {
1 , 6 , 3 , 8 , 3 , 4 , 2
};
// Get the number of elements
int n = sizeof(arr) / sizeof(arr[0]);
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
// Test
countOddXorPair(arr, n);
return 0;
}``````

#### input

`````` Array :   1  6  3  8  3  4  2
Result : 12``````
``````/*
Java program for
Count pairs with Odd XOR occurrence
*/
public class Counting
{
// Display array elements
public void printData(int[] arr, int n)
{
System.out.print("\n Array : ");
for (int i = 0; i < n; ++i)
{
// print element
System.out.print(" " + arr[i]);
}
}
public void countOddXorPair(int[] arr, int n)
{
// Display given array
this.printData(arr, n);
int odd = 0;
int even = 0;
// Counting Even and Odd occurrence in array
for (int i = 0; i < n; ++i)
{
if ((arr[i] % 2) == 0)
{
// When elements are even
even++;
}
else
{
// When elements are odd
odd++;
}
}
System.out.print("\n Result : " + odd * even);
}
public static void main(String[] args)
{
int[] arr = {
1 , 6 , 3 , 8 , 3 , 4 , 2
};
// Get the number of elements
int n = arr.length;
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
}
}``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Count pairs with Odd XOR occurrence
*/
class Counting
{
public:
// Display array elements
void printData(int arr[], int n)
{
cout << "\n Array : ";
for (int i = 0; i < n; ++i)
{
// print element
cout << " " << arr[i];
}
}
void countOddXorPair(int arr[], int n)
{
// Display given array
this->printData(arr, n);
int odd = 0;
int even = 0;
// Counting Even and Odd occurrence in array
for (int i = 0; i < n; ++i)
{
if ((arr[i] % 2) == 0)
{
// When elements are even
even++;
}
else
{
// When elements are odd
odd++;
}
}
cout << "\n Result : " << odd *even;
}
};
int main()
{
int arr[] = {
1 , 6 , 3 , 8 , 3 , 4 , 2
};
// Get the number of elements
int n = sizeof(arr) / sizeof(arr[0]);
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
return 0;
}``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````// Include namespace system
using System;
/*
Csharp program for
Count pairs with Odd XOR occurrence
*/
public class Counting
{
// Display array elements
public void printData(int[] arr, int n)
{
Console.Write("\n Array : ");
for (int i = 0; i < n; ++i)
{
// print element
Console.Write(" " + arr[i]);
}
}
public void countOddXorPair(int[] arr, int n)
{
// Display given array
this.printData(arr, n);
int odd = 0;
int even = 0;
// Counting Even and Odd occurrence in array
for (int i = 0; i < n; ++i)
{
if ((arr[i] % 2) == 0)
{
// When elements are even
even++;
}
else
{
// When elements are odd
odd++;
}
}
Console.Write("\n Result : " + odd * even);
}
public static void Main(String[] args)
{
int[] arr = {
1 , 6 , 3 , 8 , 3 , 4 , 2
};
// Get the number of elements
int n = arr.Length;
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
}
}``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````package main
import "fmt"
/*
Go program for
Count pairs with Odd XOR occurrence
*/

// Display array elements
func printData(arr[] int, n int) {
fmt.Print("\n Array : ")
for i := 0 ; i < n ; i++ {
// print element
fmt.Print(" ", arr[i])
}
}
func countOddXorPair(arr[] int, n int) {
// Display given array
printData(arr, n)
var odd int = 0
var even int = 0
// Counting Even and Odd occurrence in array
for i := 0 ; i < n ; i++ {
if (arr[i] % 2) == 0 {
// When elements are even
even++
} else {
// When elements are odd
odd++
}
}
fmt.Print("\n Result : ", odd * even)
}
func main() {

var arr = [] int {
1,
6,
3,
8,
3,
4,
2,
}
// Get the number of elements
var n int = len(arr)
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
countOddXorPair(arr, n)
}``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````<?php
/*
Php program for
Count pairs with Odd XOR occurrence
*/
class Counting
{
// Display array elements
public	function printData(\$arr, \$n)
{
echo("\n Array : ");
for (\$i = 0; \$i < \$n; ++\$i)
{
// print element
echo(" ".\$arr[\$i]);
}
}
public	function countOddXorPair(\$arr, \$n)
{
// Display given array
\$this->printData(\$arr, \$n);
\$odd = 0;
\$even = 0;
// Counting Even and Odd occurrence in array
for (\$i = 0; \$i < \$n; ++\$i)
{
if ((\$arr[\$i] % 2) == 0)
{
// When elements are even
\$even++;
}
else
{
// When elements are odd
\$odd++;
}
}
echo("\n Result : ".\$odd * \$even);
}
}

function main()
{
\$arr = array(1, 6, 3, 8, 3, 4, 2);
// Get the number of elements
\$n = count(\$arr);
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
}
main();``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````/*
Node JS program for
Count pairs with Odd XOR occurrence
*/
class Counting
{
// Display array elements
printData(arr, n)
{
process.stdout.write("\n Array : ");
for (var i = 0; i < n; ++i)
{
// print element
process.stdout.write(" " + arr[i]);
}
}
countOddXorPair(arr, n)
{
// Display given array
this.printData(arr, n);
var odd = 0;
var even = 0;
// Counting Even and Odd occurrence in array
for (var i = 0; i < n; ++i)
{
if ((arr[i] % 2) == 0)
{
// When elements are even
even++;
}
else
{
// When elements are odd
odd++;
}
}
process.stdout.write("\n Result : " + odd * even);
}
}

function main()
{
var arr = [1, 6, 3, 8, 3, 4, 2];
// Get the number of elements
var n = arr.length;
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
}
main();``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````#    Python 3 program for
#    Count pairs with Odd XOR occurrence
class Counting :
#  Display list elements
def printData(self, arr, n) :
print("\n Array : ", end = "")
i = 0
while (i < n) :
#  print element
print(" ", arr[i], end = "")
i += 1

def countOddXorPair(self, arr, n) :
#  Display given list
self.printData(arr, n)
odd = 0
even = 0
i = 0
#  Counting Even and Odd occurrence in list
while (i < n) :
if ((arr[i] % 2) == 0) :
#  When elements are even
even += 1
else :
#  When elements are odd
odd += 1

i += 1

print("\n Result : ", odd * even, end = "")

def main() :
arr = [1, 6, 3, 8, 3, 4, 2]
#  Get the number of elements
n = len(arr)
#    (1 ⊕ 6) = 7
#    (1 ⊕ 8) = 9
#    (1 ⊕ 4) = 5
#    (1 ⊕ 2) = 3
#    (6 ⊕ 3) = 5
#    (6 ⊕ 3) = 5
#    (3 ⊕ 8) = 11
#    (3 ⊕ 4) = 7
#    (3 ⊕ 2) = 1
#    (8 ⊕ 3) = 11
#    (3 ⊕ 4) = 7
#    (3 ⊕ 2) = 1
#    ---------------
#    Total : 12

if __name__ == "__main__": main()``````

#### input

`````` Array :   1  6  3  8  3  4  2
Result :  12``````
``````#    Ruby program for
#    Count pairs with Odd XOR occurrence
class Counting
#  Display array elements
def printData(arr, n)
print("\n Array : ")
i = 0
while (i < n)
#  print element
print(" ", arr[i])
i += 1
end

end

def countOddXorPair(arr, n)
#  Display given array
self.printData(arr, n)
odd = 0
even = 0
i = 0
#  Counting Even and Odd occurrence in array
while (i < n)
if ((arr[i] % 2) == 0)
#  When elements are even
even += 1
else

#  When elements are odd
odd += 1
end

i += 1
end

print("\n Result : ", odd * even)
end

end

def main()
arr = [1, 6, 3, 8, 3, 4, 2]
#  Get the number of elements
n = arr.length
#    (1 ⊕ 6) = 7
#    (1 ⊕ 8) = 9
#    (1 ⊕ 4) = 5
#    (1 ⊕ 2) = 3
#    (6 ⊕ 3) = 5
#    (6 ⊕ 3) = 5
#    (3 ⊕ 8) = 11
#    (3 ⊕ 4) = 7
#    (3 ⊕ 2) = 1
#    (8 ⊕ 3) = 11
#    (3 ⊕ 4) = 7
#    (3 ⊕ 2) = 1
#    ---------------
#    Total : 12
end

main()``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````/*
Scala program for
Count pairs with Odd XOR occurrence
*/
class Counting()
{
// Display array elements
def printData(arr: Array[Int], n: Int): Unit = {
print("\n Array : ");
var i: Int = 0;
while (i < n)
{
// print element
print(" " + arr(i));
i += 1;
}
}
def countOddXorPair(arr: Array[Int], n: Int): Unit = {
// Display given array
this.printData(arr, n);
var odd: Int = 0;
var even: Int = 0;
var i: Int = 0;
// Counting Even and Odd occurrence in array
while (i < n)
{
if ((arr(i) % 2) == 0)
{
// When elements are even
even += 1;
}
else
{
// When elements are odd
odd += 1;
}
i += 1;
}
print("\n Result : " + odd * even);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Counting = new Counting();
var arr: Array[Int] = Array(1, 6, 3, 8, 3, 4, 2);
// Get the number of elements
var n: Int = arr.length;
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
}
}``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````
``````import Foundation;
/*
Swift 4 program for
Count pairs with Odd XOR occurrence
*/
class Counting
{
// Display array elements
func printData(_ arr: [Int], _ n: Int)
{
print("\n Array : ", terminator: "");
var i: Int = 0;
while (i < n)
{
// print element
print(" ", arr[i], terminator: "");
i += 1;
}
}
func countOddXorPair(_ arr: [Int], _ n: Int)
{
// Display given array
self.printData(arr, n);
var odd: Int = 0;
var even: Int = 0;
var i: Int = 0;
// Counting Even and Odd occurrence in array
while (i < n)
{
if ((arr[i] % 2) == 0)
{
// When elements are even
even += 1;
}
else
{
// When elements are odd
odd += 1;
}
i += 1;
}
print("\n Result : ", odd * even, terminator: "");
}
}
func main()
{
let arr: [Int] = [1, 6, 3, 8, 3, 4, 2];
// Get the number of elements
let n: Int = arr.count;
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
}
main();``````

#### input

`````` Array :   1  6  3  8  3  4  2
Result :  12``````
``````/*
Kotlin program for
Count pairs with Odd XOR occurrence
*/
class Counting
{
// Display array elements
fun printData(arr: Array < Int > , n: Int): Unit
{
print("\n Array : ");
var i: Int = 0;
while (i < n)
{
// print element
print(" " + arr[i]);
i += 1;
}
}
fun countOddXorPair(arr: Array < Int > , n: Int): Unit
{
// Display given array
this.printData(arr, n);
var odd: Int = 0;
var even: Int = 0;
var i: Int = 0;
// Counting Even and Odd occurrence in array
while (i < n)
{
if ((arr[i] % 2) == 0)
{
// When elements are even
even += 1;
}
else
{
// When elements are odd
odd += 1;
}
i += 1;
}
print("\n Result : " + odd * even);
}
}
fun main(args: Array < String > ): Unit
{
val arr: Array < Int > = arrayOf(1, 6, 3, 8, 3, 4, 2);
// Get the number of elements
val n: Int = arr.count();
/*
(1 ⊕ 6) = 7
(1 ⊕ 8) = 9
(1 ⊕ 4) = 5
(1 ⊕ 2) = 3
(6 ⊕ 3) = 5
(6 ⊕ 3) = 5
(3 ⊕ 8) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
(8 ⊕ 3) = 11
(3 ⊕ 4) = 7
(3 ⊕ 2) = 1
---------------
Total : 12
*/
}``````

#### input

`````` Array :  1 6 3 8 3 4 2
Result : 12``````

## Result Explanation

Using the given input array [1, 6, 3, 8, 3, 4, 2], the countOddXorPair function calculates the number of pairs with odd XOR occurrences. In this case, it finds 12 pairs that satisfy the condition and displays the result as 12.

## Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the input array. The for-loop iterates through the array once to count odd and even occurrences, which takes linear time. Therefore, the overall time complexity is linear with respect to the input size.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post