Find the repeating and the missing element using xor
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
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