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)
	{
		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 : 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()
{
	$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 : 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 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 : 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.

New Comment