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
- Initialize two variables, 'repeated' and 'missing,' as 0.
- Calculate the XOR of all elements in the given array and store it in a variable, 'x_or.'
- Calculate the XOR of all elements in the range from 1 to n and store it in 'x_or' again.
- Find the rightmost set bit in 'x_or' and store it in 'rightMost.'
- 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.'
- 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.'
- '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 : 2Time 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.
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