Find two non repeating elements of repeated array elements
The problem is to find two non-repeating elements in an array where all other elements are repeated exactly twice. In other words, there are two unique elements in the array, and all other elements occur twice. The task is to find those two unique elements.
Example
Let's consider an array with repeated elements and two unique elements:
[5, 7, 9, 3, 1, 7, 5, 4, 1, 3]
The two unique elements in this array are 9
and 4
.
Pseudocode
Procedure displayArray(num[], n)
// Display array elements
For i = 0 to n-1
Print num[i] + " "
End For
Print new line
End Procedure
Procedure twoNonRepeatingNo(num[], n)
// Resultant x and y
x = 0
y = 0
// Calculate xor of all array elements
xorValue = num[0]
For i = 1 to n-1
xorValue = xorValue XOR num[i]
End For
// Find the value of rightmost set (active) bit
rightActiveBit = xorValue AND ~(xorValue - 1)
// Find resultant x and y non-repeated element
For i = 0 to n-1
If (num[i] AND rightActiveBit) != 0 Then
// When num[i] contains the rightmost set bit
x = x XOR num[i]
Else
// Otherwise
y = y XOR num[i]
End If
End For
// Display array elements
displayArray(num, n)
// Display calculated result
Print "Result: x =", x, ", y =", y, new line
End Procedure
// Main Function
Function main
num[] = {5, 7, 9, 3, 1, 7, 5, 4, 1, 3}
// Get number of elements in the array
n = size of num[] / size of num[0]
// Test the function
twoNonRepeatingNo(num, n)
Return 0
End Function
- Initialize two variables
x
andy
to store the two unique elements. - Calculate the XOR of all elements in the array and store it in a variable
xorValue
. - Find the rightmost set bit (active bit) in
xorValue
and store it inrightActiveBit
. - Iterate through the array again:
a. If the
rightActiveBit
is set in the current element, XOR it withx
. b. If therightActiveBit
is not set in the current element, XOR it withy
. - After the loop, the variables
x
andy
will contain the two non-repeating elements.
Algorithm Explanation
>- The XOR operation is used because it is commutative and associative. XOR of a number with itself results in
0. Therefore, when we XOR all elements in the array, the repeated elements will cancel out, and only
x
andy
will remain in the result. - After XORing all elements, the result will be a number that contains the XOR of
x
andy
. Sincex
andy
are distinct, there will be at least one set bit (1) in the result, indicating the positions wherex
andy
differ. - We find the rightmost set bit (active bit) in the result using the bitwise AND operation with its two's
complement. This operation isolates the rightmost set bit, and all other bits become zero. This is stored in
the
rightActiveBit
. - In the final loop, we separate the elements based on the
rightActiveBit
. All elements that have a set bit in the same position as therightActiveBit
will contribute to the calculation ofx
, and the others will contribute toy
.
Code Solution
Here given code implementation process.
/*
C program for
Find two non repeating elements of repeated array elements
*/
// Include header file
#include <stdio.h>
void displayArray(int num[], int n)
{
// Display array elements
for (int i = 0; i < n; ++i)
{
printf(" %d", num[i]);
}
}
void twoNonRepeatingNo(int num[], int n)
{
// Resultant x and y
int x = 0;
int y = 0;
// get first array element
int xorValue = num[0];
// Calculate xor of all array elements
for (int i = 1; i < n; ++i)
{
xorValue = xorValue ^ num[i];
}
// Find the value of rightmost set (active) bit
int rightActiveBit = xorValue & ~(xorValue - 1);
// Find resultant x and y non repeated element
for (int i = 0; i < n; ++i)
{
if ((num[i] & rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x ^ num[i];
}
else
{
// otherwise
y = y ^ num[i];
}
}
// Display array elements
displayArray(num, n);
// Display calculated result
printf("\n Result : x = %d, y = %d \n", x, y);
}
int main()
{
int num[] = {
5 , 7 , 9 , 3 , 1 , 7 , 5 , 4 , 1 , 3
};
// Get number of elements in number
int n = sizeof(num) / sizeof(num[0]);
// Test
twoNonRepeatingNo(num, n);
return 0;
}
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
// Java Program
// Find two non repeating elements of repeated array elements
class Finding
{
public void displayArray(int[] num, int n)
{
// Display array elements
for (int i = 0; i < n; ++i)
{
System.out.print(" " + num[i]);
}
}
public void twoNonRepeatingNo(int[] num, int n)
{
// Resultant x and y
int x = 0;
int y = 0;
// get first array element
int xorValue = num[0];
// Calculate xor of all array elements
for (int i = 1; i < n; ++i)
{
xorValue = xorValue ^ num[i];
}
// Find the value of rightmost set (active) bit
int rightActiveBit = xorValue & ~(xorValue - 1);
// Find resultant x and y non repeated element
for (int i = 0; i < n; ++i)
{
if ((num[i] & rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x ^ num[i];
}
else
{
// otherwise
y = y ^ num[i];
}
}
// Display array elements
this.displayArray(num, n);
// Display calculated result
System.out.print("\n Result : x = " + x + ", y = " + y + " \n");
}
public static void main(String[] args)
{
Finding task = new Finding();
// Array which contains duplicate and two non repeated element
int[] num = {
5 , 7 , 9 , 3 , 1 , 7 , 5 , 4 , 1 , 3
};
// Get number of elements in number
int n = num.length;
// Test
task.twoNonRepeatingNo(num, n);
}
}
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Find two non repeating elements of repeated array elements
class Finding
{
public: void displayArray(int num[], int n)
{
// Display array elements
for (int i = 0; i < n; ++i)
{
cout << " " << num[i];
}
}
void twoNonRepeatingNo(int num[], int n)
{
// Resultant x and y
int x = 0;
int y = 0;
// get first array element
int xorValue = num[0];
// Calculate xor of all array elements
for (int i = 1; i < n; ++i)
{
xorValue = xorValue ^ num[i];
}
// Find the value of rightmost set (active) bit
int rightActiveBit = xorValue &~(xorValue - 1);
// Find resultant x and y non repeated element
for (int i = 0; i < n; ++i)
{
if ((num[i] &rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x ^ num[i];
}
else
{
// otherwise
y = y ^ num[i];
}
}
// Display array elements
this->displayArray(num, n);
// Display calculated result
cout << "\n Result : x = " << x << ", y = " << y << " \n";
}
};
int main()
{
Finding *task = new Finding();
// Array which contains duplicate and two non repeated element
int num[] = {
5 , 7 , 9 , 3 , 1 , 7 , 5 , 4 , 1 , 3
};
// Get number of elements in number
int n = sizeof(num) / sizeof(num[0]);
// Test
task->twoNonRepeatingNo(num, n);
return 0;
}
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
// Include namespace system
using System;
// Csharp Program
// Find two non repeating elements of repeated array elements
public class Finding
{
public void displayArray(int[] num, int n)
{
// Display array elements
for (int i = 0; i < n; ++i)
{
Console.Write(" " + num[i]);
}
}
public void twoNonRepeatingNo(int[] num, int n)
{
// Resultant x and y
int x = 0;
int y = 0;
// get first array element
int xorValue = num[0];
// Calculate xor of all array elements
for (int i = 1; i < n; ++i)
{
xorValue = xorValue ^ num[i];
}
// Find the value of rightmost set (active) bit
int rightActiveBit = xorValue & ~(xorValue - 1);
// Find resultant x and y non repeated element
for (int i = 0; i < n; ++i)
{
if ((num[i] & rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x ^ num[i];
}
else
{
// otherwise
y = y ^ num[i];
}
}
// Display array elements
this.displayArray(num, n);
// Display calculated result
Console.Write("\n Result : x = " + x + ", y = " + y + " \n");
}
public static void Main(String[] args)
{
Finding task = new Finding();
// Array which contains duplicate and two non repeated element
int[] num = {
5 , 7 , 9 , 3 , 1 , 7 , 5 , 4 , 1 , 3
};
// Get number of elements in number
int n = num.Length;
// Test
task.twoNonRepeatingNo(num, n);
}
}
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
<?php
// Php Program
// Find two non repeating elements of repeated array elements
class Finding
{
public function displayArray($num, $n)
{
// Display array elements
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$num[$i]);
}
}
public function twoNonRepeatingNo($num, $n)
{
// Resultant x and y
$x = 0;
$y = 0;
// get first array element
$xorValue = $num[0];
// Calculate xor of all array elements
for ($i = 1; $i < $n; ++$i)
{
$xorValue = $xorValue ^ $num[$i];
}
// Find the value of rightmost set (active) bit
$rightActiveBit = $xorValue & ~($xorValue - 1);
// Find resultant x and y non repeated element
for ($i = 0; $i < $n; ++$i)
{
if (($num[$i] & $rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
$x = $x ^ $num[$i];
}
else
{
// otherwise
$y = $y ^ $num[$i];
}
}
// Display array elements
$this->displayArray($num, $n);
// Display calculated result
echo("\n Result : x = ".$x.
", y = ".$y.
" \n");
}
}
function main()
{
$task = new Finding();
// Array which contains duplicate and two non repeated element
$num = array(5, 7, 9, 3, 1, 7, 5, 4, 1, 3);
// Get number of elements in number
$n = count($num);
// Test
$task->twoNonRepeatingNo($num, $n);
}
main();
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
package main
import "fmt"
// Go Program
// Find two non repeating elements of repeated array elements
func displayArray(num[] int, n int) {
// Display array elements
for i := 0 ; i < n ; i++ {
fmt.Print(" ", num[i])
}
}
func twoNonRepeatingNo(num[] int, n int) {
// Resultant x and y
var x int = 0
var y int = 0
// get first array element
var xorValue int = num[0]
// Calculate xor of all array elements
for i := 1 ; i < n ; i++ {
xorValue = xorValue ^ num[i]
}
// Find the value of rightmost set (active) bit
var rightActiveBit int = xorValue & ^(xorValue - 1)
// Find resultant x and y non repeated element
for i := 0 ; i < n ; i++ {
if (num[i] & rightActiveBit) != 0 {
// When num[i] contain rightmost set bit
x = x ^ num[i]
} else {
// otherwise
y = y ^ num[i]
}
}
// Display array elements
displayArray(num, n)
// Display calculated result
fmt.Print("\n Result : x = ", x, ", y = ", y, " \n")
}
func main() {
// Array which contains duplicate and two non repeated element
var num = [] int {5, 7, 9, 3, 1, 7, 5, 4, 1, 3}
// Get number of elements in number
var n int = len(num)
// Test
twoNonRepeatingNo(num, n)
}
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
// Node JS Program
// Find two non repeating elements of repeated array elements
class Finding
{
displayArray(num, n)
{
// Display array elements
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + num[i]);
}
}
twoNonRepeatingNo(num, n)
{
// Resultant x and y
var x = 0;
var y = 0;
// get first array element
var xorValue = num[0];
// Calculate xor of all array elements
for (var i = 1; i < n; ++i)
{
xorValue = xorValue ^ num[i];
}
// Find the value of rightmost set (active) bit
var rightActiveBit = xorValue & ~(xorValue - 1);
// Find resultant x and y non repeated element
for (var i = 0; i < n; ++i)
{
if ((num[i] & rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x ^ num[i];
}
else
{
// otherwise
y = y ^ num[i];
}
}
// Display array elements
this.displayArray(num, n);
// Display calculated result
process.stdout.write("\n Result : x = " + x + ", y = " + y + " \n");
}
}
function main()
{
var task = new Finding();
// Array which contains duplicate and two non repeated element
var num = [5, 7, 9, 3, 1, 7, 5, 4, 1, 3];
// Get number of elements in number
var n = num.length;
// Test
task.twoNonRepeatingNo(num, n);
}
main();
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
# Python 3 Program
# Find two non repeating elements of repeated array elements
class Finding :
def displayArray(self, num, n) :
i = 0
# Display list elements
while (i < n) :
print(" ", num[i], end = "")
i += 1
def twoNonRepeatingNo(self, num, n) :
# Resultant x and y
x = 0
y = 0
# get first list element
xorValue = num[0]
i = 1
# Calculate xor of all list elements
while (i < n) :
xorValue = xorValue ^ num[i]
i += 1
# Find the value of rightmost set (active) bit
rightActiveBit = xorValue & ~(xorValue - 1)
i = 0
# Find resultant x and y non repeated element
while (i < n) :
if ((num[i] & rightActiveBit) != 0) :
# When num[i] contain rightmost set bit
x = x ^ num[i]
else :
# otherwise
y = y ^ num[i]
i += 1
# Display list elements
self.displayArray(num, n)
# Display calculated result
print("\n Result : x = ", x ,", y = ", y ," ")
def main() :
task = Finding()
# Array which contains duplicate and two non repeated element
num = [5, 7, 9, 3, 1, 7, 5, 4, 1, 3]
# Get number of elements in number
n = len(num)
# Test
task.twoNonRepeatingNo(num, n)
if __name__ == "__main__": main()
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9 , y = 4
# Ruby Program
# Find two non repeating elements of repeated array elements
class Finding
def displayArray(num, n)
i = 0
# Display array elements
while (i < n)
print(" ", num[i])
i += 1
end
end
def twoNonRepeatingNo(num, n)
# Resultant x and y
x = 0
y = 0
# get first array element
xorValue = num[0]
i = 1
# Calculate xor of all array elements
while (i < n)
xorValue = xorValue ^ num[i]
i += 1
end
# Find the value of rightmost set (active) bit
rightActiveBit = xorValue & ~(xorValue - 1)
i = 0
# Find resultant x and y non repeated element
while (i < n)
if ((num[i] & rightActiveBit) != 0)
# When num[i] contain rightmost set bit
x = x ^ num[i]
else
# otherwise
y = y ^ num[i]
end
i += 1
end
# Display array elements
self.displayArray(num, n)
# Display calculated result
print("\n Result : x = ", x ,", y = ", y ," \n")
end
end
def main()
task = Finding.new()
# Array which contains duplicate and two non repeated element
num = [5, 7, 9, 3, 1, 7, 5, 4, 1, 3]
# Get number of elements in number
n = num.length
# Test
task.twoNonRepeatingNo(num, n)
end
main()
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
// Scala Program
// Find two non repeating elements of repeated array elements
class Finding()
{
def displayArray(num: Array[Int], n: Int): Unit = {
var i: Int = 0;
// Display array elements
while (i < n)
{
print(" " + num(i));
i += 1;
}
}
def twoNonRepeatingNo(num: Array[Int], n: Int): Unit = {
// Resultant x and y
var x: Int = 0;
var y: Int = 0;
// get first array element
var xorValue: Int = num(0);
var i: Int = 1;
// Calculate xor of all array elements
while (i < n)
{
xorValue = xorValue ^ num(i);
i += 1;
}
// Find the value of rightmost set (active) bit
var rightActiveBit: Int = xorValue & ~(xorValue - 1);
i = 0;
// Find resultant x and y non repeated element
while (i < n)
{
if ((num(i) & rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x ^ num(i);
}
else
{
// otherwise
y = y ^ num(i);
}
i += 1;
}
// Display array elements
this.displayArray(num, n);
// Display calculated result
print("\n Result : x = " + x + ", y = " + y + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Finding = new Finding();
// Array which contains duplicate and two non repeated element
var num: Array[Int] = Array(5, 7, 9, 3, 1, 7, 5, 4, 1, 3);
// Get number of elements in number
var n: Int = num.length;
// Test
task.twoNonRepeatingNo(num, n);
}
}
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
// Swift 4 Program
// Find two non repeating elements of repeated array elements
class Finding
{
func displayArray(_ num: [Int], _ n: Int)
{
var i: Int = 0;
// Display array elements
while (i < n)
{
print(" ", num[i], terminator: "");
i += 1;
}
}
func twoNonRepeatingNo(_ num: [Int], _ n: Int)
{
// Resultant x and y
var x: Int = 0;
var y: Int = 0;
// get first array element
var xorValue: Int = num[0];
var i: Int = 1;
// Calculate xor of all array elements
while (i < n)
{
xorValue = xorValue ^ num[i];
i += 1;
}
// Find the value of rightmost set (active) bit
let rightActiveBit: Int = xorValue & ~(xorValue - 1);
i = 0;
// Find resultant x and y non repeated element
while (i < n)
{
if ((num[i] & rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x ^ num[i];
}
else
{
// otherwise
y = y ^ num[i];
}
i += 1;
}
// Display array elements
self.displayArray(num, n);
// Display calculated result
print("\n Result : x = ", x ,", y = ", y ," ");
}
}
func main()
{
let task: Finding = Finding();
// Array which contains duplicate and two non repeated element
let num: [Int] = [5, 7, 9, 3, 1, 7, 5, 4, 1, 3];
// Get number of elements in number
let n: Int = num.count;
// Test
task.twoNonRepeatingNo(num, n);
}
main();
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9 , y = 4
// Kotlin Program
// Find two non repeating elements of repeated array elements
class Finding
{
fun displayArray(num: Array < Int > , n: Int): Unit
{
var i: Int = 0;
// Display array elements
while (i < n)
{
print(" " + num[i]);
i += 1;
}
}
fun twoNonRepeatingNo(num: Array < Int > , n: Int): Unit
{
// Resultant x and y
var x: Int = 0;
var y: Int = 0;
// get first array element
var xorValue: Int = num[0];
var i: Int = 1;
// Calculate xor of all array elements
while (i < n)
{
xorValue = xorValue xor num[i];
i += 1;
}
// Find the value of rightmost set (active) bit
val rightActiveBit: Int = xorValue and(xorValue - 1).inv();
i = 0;
// Find resultant x and y non repeated element
while (i < n)
{
if ((num[i] and rightActiveBit) != 0)
{
// When num[i] contain rightmost set bit
x = x xor num[i];
}
else
{
// otherwise
y = y xor num[i];
}
i += 1;
}
// Display array elements
this.displayArray(num, n);
// Display calculated result
print("\n Result : x = " + x + ", y = " + y + " \n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Finding = Finding();
// Array which contains duplicate and two non repeated element
val num: Array < Int > = arrayOf(5, 7, 9, 3, 1, 7, 5, 4, 1, 3);
// Get number of elements in number
val n: Int = num.count();
// Test
task.twoNonRepeatingNo(num, n);
}
Output
5 7 9 3 1 7 5 4 1 3
Result : x = 9, y = 4
Time Complexity
The time complexity of this algorithm is O(n) because we iterate through the array twice: once to calculate the XOR of all elements and then to separate the unique elements based on the rightmost set bit. Both iterations take linear time, and thus the overall complexity is O(n).
Resultant Output Explanation
In the given example array [5, 7, 9, 3, 1, 7, 5, 4, 1, 3]
, the xorValue
of all
elements is 9
. The rightmost set bit in 9
is at position 0 (from the right), which
corresponds to the binary 1
. Therefore, the rightActiveBit
is 1
.
After separating elements based on the rightActiveBit
, we find x = 9
and
y = 4
, which are the two non-repeating elements in the array. The other elements, which are
repeated twice, have canceled out during the XOR operations.
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