Posted on by Kalkicode
Code Bit Logic

Find the repeating and the missing element using xor

In various scenarios, you might come across a situation where an array of integers contains one element that is repeated, and another element is missing. This problem can be efficiently solved using the XOR (exclusive OR) operation, which is a bitwise operation commonly used in programming to manipulate bits. The XOR operation is denoted by the symbol '^' and returns 1 if the bits are different and 0 if they are the same.

Problem Statement

Given an array of n integers containing elements in the range from 1 to n, find the repeating element and the missing element using XOR.

Example

Let's consider the array A = [1, 8, 5, 7, 8, 2, 6, 3]. In this array, the element 8 is repeated, and the missing element is 4. By applying the XOR operation on the array, we can efficiently identify these elements.

Pseudocode

// Function to find the repeating and missing elements in the array using XOR
function repeatingAndMissing(arr[], n):
    // Initialize variables to store the repeating and missing elements
    repeated = 0
    missing = 0

    // Calculate XOR of all elements in the given array
    x_or = arr[0]
    for i = 1 to n-1:
        x_or = x_or ^ arr[i]

    // Calculate XOR of all elements in the range from 1 to n
    for i = 1 to n:
        x_or = x_or ^ i

    // Find the rightmost set bit in the XOR result
    rightMost = ~(x_or - 1) & x_or

    // Separate elements into two groups based on the rightmost set bit
    for i = 0 to n-1:
        if (arr[i] & rightMost) == 0:
            // XOR with 'repeated' if the rightmost bit is 0
            repeated = repeated ^ arr[i]
        else:
            // XOR with 'missing' if the rightmost bit is 1
            missing = missing ^ arr[i]

    // Separate elements from 1 to n into two groups based on the rightmost set bit
    for i = 1 to n:
        if (i & rightMost) == 0:
            // XOR with 'repeated' if the rightmost bit is 0
            repeated = repeated ^ i
        else:
            // XOR with 'missing' if the rightmost bit is 1
            missing = missing ^ i

    // Print the given array elements
    print "Array Element: "
    for i = 0 to n-1:
        print arr[i]

    // Print the calculated results
    print "Missing: ", missing
    print "Repeated: ", repeated
  1. Initialize two variables, 'repeated' and 'missing,' as 0.
  2. Calculate the XOR of all elements in the given array and store it in a variable, 'x_or.'
  3. Calculate the XOR of all elements in the range from 1 to n and store it in 'x_or' again.
  4. Find the rightmost set bit in 'x_or' and store it in 'rightMost.'
  5. Loop through the array, and for each element: a. Check if the rightmost bit of the element is 0 using bitwise AND with 'rightMost.' b. If the rightmost bit is 0, XOR it with 'repeated.' c. Otherwise, XOR it with 'missing.'
  6. Loop through the range from 1 to n, and for each element: a. Check if the rightmost bit of the element is 0 using bitwise AND with 'rightMost.' b. If the rightmost bit is 0, XOR it with 'repeated.' c. Otherwise, XOR it with 'missing.'
  7. 'repeated' will now hold the repeated element, and 'missing' will hold the missing element.

Algorithm Explanation

The given algorithm leverages the property of the XOR operation that the same elements will cancel each other out when XORed. So, if we XOR all elements in the array and then XOR it with the XOR of all elements in the range from 1 to n, we will be left with the XOR of the missing and repeating elements.

Next, we need to find the rightmost set bit in the XOR result. The rightmost set bit represents the first bit where the missing and repeating elements differ. We then divide the elements into two groups based on whether the bit is set or unset, and we XOR the elements in each group separately. This way, we get the missing and repeating elements.

Code Solution

Here given code implementation process.

// C program
// Find the repeating and the missing element using xor
#include <stdio.h>

// Print the given array elements
void printArray(int arr[], int n)
{
	printf("\n Array Element");
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
}
void repeatingAndMissing(int arr[], int n)
{
	if (n < 2)
	{
		return;
	}
	// Define auxiliary variables
	int repeated = 0;
	int missing = 0;
	int i = 0;
	int x_or = arr[i];
	int rightMost = 0;
	// Perform xor operation in given array elements
	for (i = 1; i < n; ++i)
	{
		x_or = x_or ^ arr[i];
	}
	// Perform xor operation in range from 1 to n
	for (i = 1; i <= n; ++i)
	{
		x_or = x_or ^ 1;
	}
	// Find rightmost set bits
	rightMost = ~(x_or - 1) & x_or;
	for (i = 0; i < n; ++i)
	{
		if ((arr[i] & rightMost) == 0)
		{
			// When element is repeated in array
			repeated = repeated ^ arr[i];
		}
		else
		{
			// When element is missing in array
			missing = missing ^ arr[i];
		}
	}
	for (i = 1; i <= n; ++i)
	{
		if ((i & rightMost) == 0)
		{
			// When element is repeated in range (1...n)
			repeated = repeated ^ i;
		}
		else
		{
			// When element is missing in range (1...n)
			missing = missing ^ i;
		}
	}
	printArray(arr, n);
	// Display calculated result
	printf("\n Missing  : %d", missing);
	printf("\n Repeated : %d\n", repeated);
}
int main()
{
	int arr1[] = {
		1 , 8 , 5 , 7 , 8 , 2 , 6 , 3
	};
	// Get the size of array arr1
	int n = sizeof(arr1) / sizeof(arr1[0]);
	repeatingAndMissing(arr1, n);
	int arr2[] = {
		1 , 4 , 3 , 3
	};
	// Get the size of array arr2
	n = sizeof(arr2) / sizeof(arr2[0]);
	repeatingAndMissing(arr2, n);
	return 0;
}

input

 Array Element  1  8  5  7  8  2  6  3
 Missing  : 4
 Repeated : 8

 Array Element  1  4  3  3
 Missing  : 3
 Repeated : 2
/*
  Java Program for
  Find the repeating and the missing element using xor
*/
class Finding
{
	// Print the given array elements
	public void printArray(int[] arr, int n)
	{
		System.out.print("\n Array Element");
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	public void repeatingAndMissing(int[] arr, int n)
	{
		if (n < 2)
		{
			return;
		}
		// Define auxiliary variables
		int repeated = 0;
		int missing = 0;
		int i = 0;
		int x_or = arr[i];
		int rightMost = 0;
		// Perform xor operation in given array elements
		for (i = 1; i < n; ++i)
		{
			x_or = x_or ^ arr[i];
		}
		// Perform xor operation in range from 1 to n
		for (i = 1; i <= n; ++i)
		{
			x_or = x_or ^ 1;
		}
		// Find rightmost set bits
		rightMost = ~(x_or - 1) & x_or;
		for (i = 0; i < n; ++i)
		{
			if ((arr[i] & rightMost) == 0)
			{
				// When element is repeated in array
				repeated = repeated ^ arr[i];
			}
			else
			{
				// When element is missing in array
				missing = missing ^ arr[i];
			}
		}
		for (i = 1; i <= n; ++i)
		{
			if ((i & rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				repeated = repeated ^ i;
			}
			else
			{
				// When element is missing in range (1...n)
				missing = missing ^ i;
			}
		}
		printArray(arr, n);
		// Display calculated result
		System.out.println("\n Missing : " + missing);
		System.out.println(" Repeated : " + repeated);
	}
	public static void main(String[] args)
	{
		Finding task = new Finding();
		int[] arr1 = {
			1 , 8 , 5 , 7 , 8 , 2 , 6 , 3
		};
		// Get the size of array arr1
		int n = arr1.length;
		task.repeatingAndMissing(arr1, n);
		int[] arr2 = {
			1 , 4 , 3 , 3
		};
		// Get the size of array arr2
		n = arr2.length;
		task.repeatingAndMissing(arr2, n);
	}
}

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  Find the repeating and the missing element using xor
*/
class Finding
{
	public:
		// Print the given array elements
		void printArray(int arr[], int n)
		{
			cout << "\n Array Element";
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
		}
	void repeatingAndMissing(int arr[], int n)
	{
		if (n < 2)
		{
			return;
		}
		// Define auxiliary variables
		int repeated = 0;
		int missing = 0;
		int i = 0;
		int x_or = arr[i];
		int rightMost = 0;
		// Perform xor operation in given array elements
		for (i = 1; i < n; ++i)
		{
			x_or = x_or ^ arr[i];
		}
		// Perform xor operation in range from 1 to n
		for (i = 1; i <= n; ++i)
		{
			x_or = x_or ^ 1;
		}
		// Find rightmost set bits
		rightMost = ~(x_or - 1) &x_or;
		for (i = 0; i < n; ++i)
		{
			if ((arr[i] &rightMost) == 0)
			{
				// When element is repeated in array
				repeated = repeated ^ arr[i];
			}
			else
			{
				// When element is missing in array
				missing = missing ^ arr[i];
			}
		}
		for (i = 1; i <= n; ++i)
		{
			if ((i &rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				repeated = repeated ^ i;
			}
			else
			{
				// When element is missing in range (1...n)
				missing = missing ^ i;
			}
		}
		this->printArray(arr, n);
		// Display calculated result
		cout << "\n Missing : " << missing << endl;
		cout << " Repeated : " << repeated << endl;
	}
};
int main()
{
	Finding *task = new Finding();
	int arr1[] = {
		1 , 8 , 5 , 7 , 8 , 2 , 6 , 3
	};
	// Get the size of array arr1
	int n = sizeof(arr1) / sizeof(arr1[0]);
	task->repeatingAndMissing(arr1, n);
	int arr2[] = {
		1 , 4 , 3 , 3
	};
	// Get the size of array arr2
	n = sizeof(arr2) / sizeof(arr2[0]);
	task->repeatingAndMissing(arr2, n);
	return 0;
}

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2
// Include namespace system
using System;
/*
  Csharp Program for
  Find the repeating and the missing element using xor
*/
public class Finding
{
	// Print the given array elements
	public void printArray(int[] arr, int n)
	{
		Console.Write("\n Array Element");
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	public void repeatingAndMissing(int[] arr, int n)
	{
		if (n < 2)
		{
			return;
		}
		// Define auxiliary variables
		int repeated = 0;
		int missing = 0;
		int i = 0;
		int x_or = arr[i];
		int rightMost = 0;
		// Perform xor operation in given array elements
		for (i = 1; i < n; ++i)
		{
			x_or = x_or ^ arr[i];
		}
		// Perform xor operation in range from 1 to n
		for (i = 1; i <= n; ++i)
		{
			x_or = x_or ^ 1;
		}
		// Find rightmost set bits
		rightMost = ~(x_or - 1) & x_or;
		for (i = 0; i < n; ++i)
		{
			if ((arr[i] & rightMost) == 0)
			{
				// When element is repeated in array
				repeated = repeated ^ arr[i];
			}
			else
			{
				// When element is missing in array
				missing = missing ^ arr[i];
			}
		}
		for (i = 1; i <= n; ++i)
		{
			if ((i & rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				repeated = repeated ^ i;
			}
			else
			{
				// When element is missing in range (1...n)
				missing = missing ^ i;
			}
		}
		this.printArray(arr, n);
		// Display calculated result
		Console.WriteLine("\n Missing : " + missing);
		Console.WriteLine(" Repeated : " + repeated);
	}
	public static void Main(String[] args)
	{
		Finding task = new Finding();
		int[] arr1 = {
			1 , 8 , 5 , 7 , 8 , 2 , 6 , 3
		};
		// Get the size of array arr1
		int n = arr1.Length;
		task.repeatingAndMissing(arr1, n);
		int[] arr2 = {
			1 , 4 , 3 , 3
		};
		// Get the size of array arr2
		n = arr2.Length;
		task.repeatingAndMissing(arr2, n);
	}
}

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2
<?php
/*
  Php Program for
  Find the repeating and the missing element using xor
*/
class Finding
{
	// Print the given array elements
	public	function printArray($arr, $n)
	{
		echo "\n Array Element";
		for ($i = 0; $i < $n; ++$i)
		{
			echo " ".$arr[$i];
		}
	}
	public	function repeatingAndMissing($arr, $n)
	{
		if ($n < 2)
		{
			return;
		}
		// Define auxiliary variables
		$repeated = 0;
		$missing = 0;
		$i = 0;
		$x_or = $arr[$i];
		$rightMost = 0;
		// Perform xor operation in given array elements
		for ($i = 1; $i < $n; ++$i)
		{
			$x_or = $x_or ^ $arr[$i];
		}
		// Perform xor operation in range from 1 to n
		for ($i = 1; $i <= $n; ++$i)
		{
			$x_or = $x_or ^ 1;
		}
		// Find rightmost set bits
		$rightMost = ~($x_or - 1) & $x_or;
		for ($i = 0; $i < $n; ++$i)
		{
			if (($arr[$i] & $rightMost) == 0)
			{
				// When element is repeated in array
				$repeated = $repeated ^ $arr[$i];
			}
			else
			{
				// When element is missing in array
				$missing = $missing ^ $arr[$i];
			}
		}
		for ($i = 1; $i <= $n; ++$i)
		{
			if (($i & $rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				$repeated = $repeated ^ $i;
			}
			else
			{
				// When element is missing in range (1...n)
				$missing = $missing ^ $i;
			}
		}
		$this->printArray($arr, $n);
		// Display calculated result
		echo "\n Missing : ".$missing.
		"\n";
		echo " Repeated : ".$repeated.
		"\n";
	}
}

function main()
{
	$task = new Finding();
	$arr1 = array(1, 8, 5, 7, 8, 2, 6, 3);
	// Get the size of array arr1
	$n = count($arr1);
	$task->repeatingAndMissing($arr1, $n);
	$arr2 = array(1, 4, 3, 3);
	// Get the size of array arr2
	$n = count($arr2);
	$task->repeatingAndMissing($arr2, $n);
}
main();

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2
/*
  Node JS Program for
  Find the repeating and the missing element using xor
*/
class Finding
{
	// Print the given array elements
	printArray(arr, n)
	{
		process.stdout.write("\n Array Element");
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	repeatingAndMissing(arr, n)
	{
		if (n < 2)
		{
			return;
		}
		// Define auxiliary variables
		var repeated = 0;
		var missing = 0;
		var i = 0;
		var x_or = arr[i];
		var rightMost = 0;
		// Perform xor operation in given array elements
		for (i = 1; i < n; ++i)
		{
			x_or = x_or ^ arr[i];
		}
		// Perform xor operation in range from 1 to n
		for (i = 1; i <= n; ++i)
		{
			x_or = x_or ^ 1;
		}
		// Find rightmost set bits
		rightMost = ~(x_or - 1) & x_or;
		for (i = 0; i < n; ++i)
		{
			if ((arr[i] & rightMost) == 0)
			{
				// When element is repeated in array
				repeated = repeated ^ arr[i];
			}
			else
			{
				// When element is missing in array
				missing = missing ^ arr[i];
			}
		}
		for (i = 1; i <= n; ++i)
		{
			if ((i & rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				repeated = repeated ^ i;
			}
			else
			{
				// When element is missing in range (1...n)
				missing = missing ^ i;
			}
		}
		this.printArray(arr, n);
		// Display calculated result
		console.log("\n Missing : " + missing);
		console.log(" Repeated : " + repeated);
	}
}

function main()
{
	var task = new Finding();
	var arr1 = [1, 8, 5, 7, 8, 2, 6, 3];
	// Get the size of array arr1
	var n = arr1.length;
	task.repeatingAndMissing(arr1, n);
	var arr2 = [1, 4, 3, 3];
	// Get the size of array arr2
	n = arr2.length;
	task.repeatingAndMissing(arr2, n);
}
main();

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2
#  Python 3 Program for
#  Find the repeating and the missing element using xor
class Finding :
	#  Print the given list elements
	def printArray(self, arr, n) :
		print("\n Array Element", end = "")
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	def repeatingAndMissing(self, arr, n) :
		if (n < 2) :
			return
		
		repeated = 0
		missing = 0
		i = 0
		x_or = arr[i]
		rightMost = 0
		#  Perform xor operation in given list elements
		i = 1
		while (i < n) :
			x_or = x_or ^ arr[i]
			i += 1
		
		#  Perform xor operation in range from 1 to n
		i = 1
		while (i <= n) :
			x_or = x_or ^ 1
			i += 1
		
		#  Find rightmost set bits
		rightMost = ~(x_or - 1) & x_or
		i = 0
		while (i < n) :
			if ((arr[i] & rightMost) == 0) :
				#  When element is repeated in list
				repeated = repeated ^ arr[i]
			else :
				#  When element is missing in list
				missing = missing ^ arr[i]
			
			i += 1
		
		i = 1
		while (i <= n) :
			if ((i & rightMost) == 0) :
				#  When element is repeated in range (1...n)
				repeated = repeated ^ i
			else :
				#  When element is missing in range (1...n)
				missing = missing ^ i
			
			i += 1
		
		self.printArray(arr, n)
		#  Display calculated result
		print("\n Missing : ", missing)
		print(" Repeated : ", repeated)
	

def main() :
	task = Finding()
	arr1 = [1, 8, 5, 7, 8, 2, 6, 3]
	n = len(arr1)
	task.repeatingAndMissing(arr1, n)
	arr2 = [1, 4, 3, 3]
	#  Get the size of list arr2
	n = len(arr2)
	task.repeatingAndMissing(arr2, n)

if __name__ == "__main__": main()

input

 Array Element  1  8  5  7  8  2  6  3
 Missing :  4
 Repeated :  8

 Array Element  1  4  3  3
 Missing :  3
 Repeated :  2
#  Ruby Program for
#  Find the repeating and the missing element using xor
class Finding 
	#  Print the given array elements
	def printArray(arr, n) 
		print("\n Array Element")
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	def repeatingAndMissing(arr, n) 
		if (n < 2) 
			return
		end

		#  Define auxiliary variables
		repeated = 0
		missing = 0
		i = 0
		x_or = arr[i]
		rightMost = 0
		#  Perform xor operation in given array elements
		i = 1
		while (i < n) 
			x_or = x_or ^ arr[i]
			i += 1
		end

		#  Perform xor operation in range from 1 to n
		i = 1
		while (i <= n) 
			x_or = x_or ^ 1
			i += 1
		end

		#  Find rightmost set bits
		rightMost = ~(x_or - 1) & x_or
		i = 0
		while (i < n) 
			if ((arr[i] & rightMost) == 0) 
				#  When element is repeated in array
				repeated = repeated ^ arr[i]
			else 
				#  When element is missing in array
				missing = missing ^ arr[i]
			end

			i += 1
		end

		i = 1
		while (i <= n) 
			if ((i & rightMost) == 0) 
				#  When element is repeated in range (1...n)
				repeated = repeated ^ i
			else 
				#  When element is missing in range (1...n)
				missing = missing ^ i
			end

			i += 1
		end

		self.printArray(arr, n)
		#  Display calculated result
		print("\n Missing : ", missing, "\n")
		print(" Repeated : ", repeated, "\n")
	end

end

def main() 
	task = Finding.new()
	arr1 = [1, 8, 5, 7, 8, 2, 6, 3]
	#  Get the size of array arr1
	n = arr1.length
	task.repeatingAndMissing(arr1, n)
	arr2 = [1, 4, 3, 3]
	#  Get the size of array arr2
	n = arr2.length
	task.repeatingAndMissing(arr2, n)
end

main()

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2
/*
  Scala Program for
  Find the repeating and the missing element using xor
*/
class Finding()
{
	// Print the given array elements
	def printArray(arr: Array[Int], n: Int): Unit = {
		print("\n Array Element");
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	def repeatingAndMissing(arr: Array[Int], n: Int): Unit = {
		if (n < 2)
		{
			return;
		}
		// Define auxiliary variables
		var repeated: Int = 0;
		var missing: Int = 0;
		var i: Int = 0;
		var x_or: Int = arr(i);
		var rightMost: Int = 0;
		// Perform xor operation in given array elements
		i = 1;
		while (i < n)
		{
			x_or = x_or ^ arr(i);
			i += 1;
		}
		// Perform xor operation in range from 1 to n
		i = 1;
		while (i <= n)
		{
			x_or = x_or ^ 1;
			i += 1;
		}
		// Find rightmost set bits
		rightMost = ~(x_or - 1) & x_or;
		i = 0;
		while (i < n)
		{
			if ((arr(i) & rightMost) == 0)
			{
				// When element is repeated in array
				repeated = repeated ^ arr(i);
			}
			else
			{
				// When element is missing in array
				missing = missing ^ arr(i);
			}
			i += 1;
		}
		i = 1;
		while (i <= n)
		{
			if ((i & rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				repeated = repeated ^ i;
			}
			else
			{
				// When element is missing in range (1...n)
				missing = missing ^ i;
			}
			i += 1;
		}
		printArray(arr, n);
		// Display calculated result
		println("\n Missing : " + missing);
		println(" Repeated : " + repeated);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Finding = new Finding();
		var arr1: Array[Int] = Array(1, 8, 5, 7, 8, 2, 6, 3);
		// Get the size of array arr1
		var n: Int = arr1.length;
		task.repeatingAndMissing(arr1, n);
		var arr2: Array[Int] = Array(1, 4, 3, 3);
		// Get the size of array arr2
		n = arr2.length;
		task.repeatingAndMissing(arr2, n);
	}
}

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2
/*
  Swift 4 Program for
  Find the repeating and the missing element using xor
*/
class Finding
{
	// Print the given array elements
	func printArray(_ arr: [Int], _ n: Int)
	{
		print("\n Array Element", terminator: "");
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	func repeatingAndMissing(_ arr: [Int], _ n: Int)
	{
		if (n < 2)
		{
			return;
		}
		// Define auxiliary variables
		var repeated: Int = 0;
		var missing: Int = 0;
		var i: Int = 0;
		var x_or: Int = arr[i];
		var rightMost: Int = 0;
		// Perform xor operation in given array elements
		i = 1;
		while (i < n)
		{
			x_or = x_or ^ arr[i];
			i += 1;
		}
		// Perform xor operation in range from 1 to n
		i = 1;
		while (i <= n)
		{
			x_or = x_or ^ 1;
			i += 1;
		}
		// Find rightmost set bits
		rightMost = ~(x_or - 1) & x_or;
		i = 0;
		while (i < n)
		{
			if ((arr[i] & rightMost) == 0)
			{
				// When element is repeated in array
				repeated = repeated ^ arr[i];
			}
			else
			{
				// When element is missing in array
				missing = missing ^ arr[i];
			}
			i += 1;
		}
		i = 1;
		while (i <= n)
		{
			if ((i & rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				repeated = repeated ^ i;
			}
			else
			{
				// When element is missing in range (1...n)
				missing = missing ^ i;
			}
			i += 1;
		}
		self.printArray(arr, n);
		// Display calculated result
		print("\n Missing : ", missing);
		print(" Repeated : ", repeated);
	}
}
func main()
{
	let task: Finding = Finding();
	let arr1: [Int] = [1, 8, 5, 7, 8, 2, 6, 3];
	// Get the size of array arr1
	var n: Int = arr1.count;
	task.repeatingAndMissing(arr1, n);
	let arr2: [Int] = [1, 4, 3, 3];
	// Get the size of array arr2
	n = arr2.count;
	task.repeatingAndMissing(arr2, n);
}
main();

input

 Array Element  1  8  5  7  8  2  6  3
 Missing :  4
 Repeated :  8

 Array Element  1  4  3  3
 Missing :  3
 Repeated :  2
/*
  Kotlin Program for
  Find the repeating and the missing element using xor
*/
class Finding
{
	// Print the given array elements
	fun printArray(arr: Array < Int > , n: Int): Unit
	{
		print("\n Array Element");
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	fun repeatingAndMissing(arr: Array < Int > , n: Int): Unit
	{
		if (n < 2)
		{
			return;
		}
		// Define auxiliary variables
		var repeated: Int = 0;
		var missing: Int = 0;
		var i: Int = 0;
		var x_or: Int = arr[i];
		var rightMost: Int;
		i = 1;
		while (i < n)
		{
			x_or = x_or xor arr[i];
			i += 1;
		}
		i = 1;
		while (i <= n)
		{
			x_or = x_or xor 1;
			i += 1;
		}
		// Find rightmost set bits
		rightMost = (x_or - 1).inv() and x_or;
		i = 0;
		while (i < n)
		{
			if ((arr[i] and rightMost) == 0)
			{
				// When element is repeated in array
				repeated = repeated xor arr[i];
			}
			else
			{
				// When element is missing in array
				missing = missing xor arr[i];
			}
			i += 1;
		}
		i = 1;
		while (i <= n)
		{
			if ((i and rightMost) == 0)
			{
				// When element is repeated in range (1...n)
				repeated = repeated xor i;
			}
			else
			{
				// When element is missing in range (1...n)
				missing = missing xor i;
			}
			i += 1;
		}
		this.printArray(arr, n);
		// Display calculated result
		println("\n Missing : " + missing);
		println(" Repeated : " + repeated);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Finding = Finding();
	val arr1: Array < Int > = arrayOf(1, 8, 5, 7, 8, 2, 6, 3);
	// Get the size of array arr1
	var n: Int = arr1.count();
	task.repeatingAndMissing(arr1, n);
	val arr2: Array < Int > = arrayOf(1, 4, 3, 3);
	// Get the size of array arr2
	n = arr2.count();
	task.repeatingAndMissing(arr2, n);
}

input

 Array Element 1 8 5 7 8 2 6 3
 Missing : 4
 Repeated : 8

 Array Element 1 4 3 3
 Missing : 3
 Repeated : 2

Time Complexity

The time complexity of this algorithm is O(n) as it requires two passes through the array of n elements. This makes it efficient in finding the repeating and missing elements using XOR.

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