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
- Initialize variables "odd" and "even" to 0.
- 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.
- The result will be the product of "odd" and "even".
Algorithm
- Start
- Define a function countOddXorPair(arr[], n):
- Initialize variables odd = 0 and even = 0.
- Iterate i from 0 to n-1: a. If (arr[i] % 2) == 0, increment even by 1. b. Else, increment odd by 1.
- Print the given array elements using printData function.
- Calculate the result by multiplying odd and even.
- Print the result.
- 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)
{
Counting task = new Counting();
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
*/
task.countOddXorPair(arr, n);
}
}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()
{
Counting *task = new Counting();
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
*/
task->countOddXorPair(arr, n);
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)
{
Counting task = new Counting();
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
*/
task.countOddXorPair(arr, n);
}
}input
Array : 1 6 3 8 3 4 2
Result : 12package 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()
{
$task = new Counting();
$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
*/
$task->countOddXorPair($arr, $n);
}
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 task = new Counting();
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
*/
task.countOddXorPair(arr, n);
}
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() :
task = Counting()
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
task.countOddXorPair(arr, n)
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()
task = Counting.new()
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
task.countOddXorPair(arr, n)
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
*/
task.countOddXorPair(arr, n);
}
}input
Array : 1 6 3 8 3 4 2
Result : 12import 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 task: Counting = Counting();
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
*/
task.countOddXorPair(arr, n);
}
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 task: Counting = Counting();
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
*/
task.countOddXorPair(arr, n);
}input
Array : 1 6 3 8 3 4 2
Result : 12Result 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.
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.
New Comment