# Find even occurring elements in an array of limited range

The problem Find even occurring elements in an array of limited range involves identifying the elements that occur an even number of times in an array of integers within a specific range (0 to 31). The goal is to find the elements that appear an even number of times and print them.

## Problem Statement and Description

Given an array of integers where each element is within the range of 0 to 31, the task is to identify and print the elements that occur an even number of times in the array. It's important to note that the elements are within this limited range.

## Example

Consider the array `[7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7]`. The even occurring elements in this array are 7, 1, 5, and 0.

• The element `7` appears 4 times, which is an even number.
• The element `8` appears 1 time, which is an odd number.
• The element `9` appears 3 times, which is an odd number.
• The element `1` appears 2 times, which is an even number.
• The element `2` appears 1 time, which is an odd number.
• The element `5` appears 2 times, which is an even number.
• The element `0` appears 2 times, which is an even number.
• The element `3` appears 1 time, which is an odd number.

## Idea to Solve the Problem

The key idea is to use bitwise XOR operations to find the elements that occur an even number of times. Since XOR of an element with itself is 0, an even number of occurrences will cancel each other out, resulting in the XOR value of 0. This property can be utilized to find the even occurring elements.

## Pseudocode

Here's the pseudocode for the algorithm:

``````function repeatedEvenTerm(data, n):
xors = 0
for i = 0 to n - 1:
if data[i] is outside the range 0 to 31:
print "Limits are Exceeded"
return
location = 1 << data[i]
xors = xors XOR location
for i = 0 to n - 1:
location = 1 << data[i]
if location AND xors is 0:
print data[i]
xors = xors XOR location``````

## Algorithm Explanation

1. The function `repeatedEvenTerm(data, n)` takes an array `data` of integers and its length `n` as inputs.
2. It initializes the `xors` variable to 0, which will be used to find the even occurring elements using bitwise XOR operations.
3. The first loop iterates through each element in the array.
4. For each element, the algorithm checks whether it's within the valid range (0 to 31).
5. If the element is within the range, the algorithm calculates the `location` using bitwise left shift operation (`1 << data[i]`).
6. The algorithm performs the XOR operation between the current `xors` value and the calculated `location`, updating the `xors` value accordingly.
7. After the first loop, the `xors` value will represent the XOR of elements occurring an odd number of times.
8. The second loop iterates through each element again.
9. For each element, the algorithm checks whether the `location` AND `xors` value is 0.
10. If the condition is satisfied, it means that the element occurs an even number of times, and it's printed.
11. The `xors` value is then updated by performing the XOR operation with the current `location`.
12. The function terminates after processing all elements.

## Code Solution

``````// C Program
// Find even occurring elements in an array of limited range
// Element value between 0 to 31
#include <stdio.h>

void repeatedEvenTerm(int data[], int n)
{
// Define some auxiliary resultant variable
int location = 0;
// This is used to determine number which is occurring Even number of times
int xors = 0;
// Loop controlling variable i
int i = 0;
// Execute loop through by array size
for (i = 0; i < n; ++i)
{
if (data[i] < 0 || data[i] > 31)
{
printf("\n Limits are Exceeded ");
return;
}
// Left shift of number 1 by array element
location = 1 << data[i];
// Calculate xor of previous result and new bit location
xors = xors ^ location;
}
// Execute loop through by array size n
for (i = 0; i < n; ++i)
{
// Left shift of number 1 by array element
location = 1 << data[i];
if (!(location & xors))
{
printf("   %d", data[i]);
// reset position
xors = xors ^ location;
}
}
}
int main(int argc, char
const *argv[])
{
// Define array of integer element
int data[] = {
7 , 8 , 9 , 1 , 7 , 2 , 5 , 9 , 7 , 0 , 3 , 9 , 5 , 0 , 1 , 7
};
// Get the size of array
int n = sizeof(data) / sizeof(data);
repeatedEvenTerm(data, n);
return 0;
}``````

#### Output

``   7   1   5   0``
``````/*
Java program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
public class Counting
{
public void repeatedEvenTerm(int[] data, int n)
{
// Define some auxiliary resultant variable
int location = 0;
// This is used to determine number which is occurring Even number of times
int xors = 0;
// Loop controlling variable i
int i = 0;
// Execute loop through by array size
for (i = 0; i < n; ++i)
{
if (data[i] < 0 || data[i] > 31)
{
System.out.print("\n Limits are Exceeded ");
return;
}
// Left shift of number 1 by array element
location = 1 << data[i];
// Calculate xor of previous result and new bit location
xors = xors ^ location;
}
// Execute loop through by array size n
for (i = 0; i < n; ++i)
{
// Left shift of number 1 by array element
location = 1 << data[i];
if ((location & xors)==0)
{
System.out.print(" " + data[i]);
// reset position
xors = xors ^ location;
}
}
}
public static void main(String[] args)
{
// Define array of integer element
int[] data = {
7 , 8 , 9 , 1 , 7 , 2 , 5 , 9 , 7 , 0 , 3 , 9 , 5 , 0 , 1 , 7
};
// Get the size of array
int n = data.length;
}
}``````

#### Output

`` 7 1 5 0``
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
class Counting
{
public: void repeatedEvenTerm(int data[], int n)
{
// Define some auxiliary resultant variable
int location = 0;
// This is used to determine number which is occurring Even number of times
int xors = 0;
// Loop controlling variable i
int i = 0;
// Execute loop through by array size
for (i = 0; i < n; ++i)
{
if (data[i] < 0 || data[i] > 31)
{
cout << "\n Limits are Exceeded ";
return;
}
// Left shift of number 1 by array element
location = 1 << data[i];
// Calculate xor of previous result and new bit location
xors = xors ^ location;
}
// Execute loop through by array size n
for (i = 0; i < n; ++i)
{
// Left shift of number 1 by array element
location = 1 << data[i];
if ((location &xors) == 0)
{
cout << " " << data[i];
// reset position
xors = xors ^ location;
}
}
}
};
int main()
{
// Define array of integer element
int data[] = {
7 , 8 , 9 , 1 , 7 , 2 , 5 , 9 , 7 , 0 , 3 , 9 , 5 , 0 , 1 , 7
};
// Get the size of array
int n = sizeof(data) / sizeof(data);
return 0;
}``````

#### Output

`` 7 1 5 0``
``````// Include namespace system
using System;
/*
C# program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
public class Counting
{
public void repeatedEvenTerm(int[] data, int n)
{
// Define some auxiliary resultant variable
int location = 0;
// This is used to determine number which is occurring Even number of times
int xors = 0;
// Loop controlling variable i
int i = 0;
// Execute loop through by array size
for (i = 0; i < n; ++i)
{
if (data[i] < 0 || data[i] > 31)
{
Console.Write("\n Limits are Exceeded ");
return;
}
// Left shift of number 1 by array element
location = 1 << data[i];
// Calculate xor of previous result and new bit location
xors = xors ^ location;
}
// Execute loop through by array size n
for (i = 0; i < n; ++i)
{
// Left shift of number 1 by array element
location = 1 << data[i];
if ((location & xors) == 0)
{
Console.Write(" " + data[i]);
// reset bit position
xors = xors ^ location;
}
}
}
public static void Main(String[] args)
{
// Define array of integer element
int[] data = {
7 , 8 , 9 , 1 , 7 , 2 , 5 , 9 , 7 , 0 , 3 , 9 , 5 , 0 , 1 , 7
};
// Get the size of array
int n = data.Length;
}
}``````

#### Output

`` 7 1 5 0``
``````<?php
/*
Php program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
class Counting
{
public	function repeatedEvenTerm( & \$data, \$n)
{
// Define some auxiliary resultant variable
\$location = 0;
// This is used to determine number which is occurring Even number of times
\$xors = 0;
// Loop controlling variable i
\$i = 0;
// Execute loop through by array size
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$data[\$i] < 0 || \$data[\$i] > 31)
{
echo "\n Limits are Exceeded ";
return;
}
// Left shift of number 1 by array element
\$location = 1 << \$data[\$i];
// Calculate xor of previous result and new bit location
\$xors = \$xors ^ \$location;
}
// Execute loop through by array size n
for (\$i = 0; \$i < \$n; ++\$i)
{
// Left shift of number 1 by array element
\$location = 1 << \$data[\$i];
if ((\$location & \$xors) == 0)
{
echo " ". \$data[\$i];
// reset bit position
\$xors = \$xors ^ \$location;
}
}
}
}

function main()
{
// Define array of integer element
\$data = array(7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7);
// Get the size of array
\$n = count(\$data);
}
main();``````

#### Output

`` 7 1 5 0``
``````/*
Node Js program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
class Counting
{
repeatedEvenTerm(data, n)
{
// Define some auxiliary resultant variable
var location = 0;
// This is used to determine number which is occurring Even number of times
var xors = 0;
// Loop controlling variable i
var i = 0;
// Execute loop through by array size
for (i = 0; i < n; ++i)
{
if (data[i] < 0 || data[i] > 31)
{
process.stdout.write("\n Limits are Exceeded ");
return;
}
// Left shift of number 1 by array element
location = 1 << data[i];
// Calculate xor of previous result and new bit location
xors = xors ^ location;
}
// Execute loop through by array size n
for (i = 0; i < n; ++i)
{
// Left shift of number 1 by array element
location = 1 << data[i];
if ((location & xors) == 0)
{
process.stdout.write(" " + data[i]);
// reset bit position
xors = xors ^ location;
}
}
}
}

function main()
{
// Define array of integer element
var data = [7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7];
// Get the size of array
var n = data.length;
}
main();``````

#### Output

`` 7 1 5 0``
``````#   Python 3 program
#   Find even occurring elements in an array of limited range
#   Element value between 0 to 31

class Counting :
def repeatedEvenTerm(self, data, n) :
#  Define some auxiliary resultant variable
location = 0
#  This is used to determine number which is occurring Even number of times
xors = 0
#  Loop controlling variable i
i = 0
#  Execute loop through by list size
while (i < n) :
if (data[i] < 0 or data[i] > 31) :
print("\n Limits are Exceeded ", end = "")
return

#  Left shift of number 1 by list element
location = 1 << data[i]
#  Calculate xor of previous result and new bit location
xors = xors ^ location
i += 1

#  Execute loop through by list size n
i = 0
while (i < n) :
#  Left shift of number 1 by list element
location = 1 << data[i]
if ((location & xors) == 0) :
print(" ", data[i], end = "")
#  reset bit position
xors = xors ^ location

i += 1

def main() :
#  Define list of integer element
data = [7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7]
#  Get the size of list
n = len(data)

if __name__ == "__main__": main()``````

#### Output

``  7  1  5  0``
``````#   Ruby program
#   Find even occurring elements in an array of limited range
#   Element value between 0 to 31

class Counting
def repeatedEvenTerm(data, n)
#  Define some auxiliary resultant variable
location = 0
#  This is used to determine number which is occurring Even number of times
xors = 0
#  Loop controlling variable i
i = 0
#  Execute loop through by array size
while (i < n)
if (data[i] < 0 || data[i] > 31)
print("\n Limits are Exceeded ")
return
end

#  Left shift of number 1 by array element
location = 1 << data[i]
#  Calculate xor of previous result and new bit location
xors = xors ^ location
i += 1
end

#  Execute loop through by array size n
i = 0
while (i < n)
#  Left shift of number 1 by array element
location = 1 << data[i]
if ((location & xors) == 0)
print(" ", data[i])
#  reset bit position
xors = xors ^ location
end

i += 1
end

end

end

def main()
#  Define array of integer element
data = [7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7]
#  Get the size of array
n = data.length
end

main()``````

#### Output

`` 7 1 5 0``
``````/*
Scala program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
class Counting
{
def repeatedEvenTerm(data: Array[Int], n: Int): Unit = {
// Define some auxiliary resultant variable
var location: Int = 0;
// This is used to determine number which is occurring Even number of times
var xors: Int = 0;
// Loop controlling variable i
var i: Int = 0;
// Execute loop through by array size
while (i < n)
{
if (data(i) < 0 || data(i) > 31)
{
print("\n Limits are Exceeded ");
return;
}
// Left shift of number 1 by array element
location = 1 << data(i);
// Calculate xor of previous result and new bit location
xors = xors ^ location;
i += 1;
}
// Execute loop through by array size n
i = 0;
while (i < n)
{
// Left shift of number 1 by array element
location = 1 << data(i);
if ((location & xors) == 0)
{
print(" " + data(i));
// reset bit position
xors = xors ^ location;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Counting = new Counting();
// Define array of integer element
var data: Array[Int] = Array(7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7);
// Get the size of array
var n: Int = data.length;
}
}``````

#### Output

`` 7 1 5 0``
``````/*
Swift 4 program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
class Counting
{
func repeatedEvenTerm(_ data: [Int], _ n: Int)
{
// Define some auxiliary resultant variable
var location: Int = 0;
// This is used to determine number which is occurring Even number of times
var xors: Int = 0;
// Loop controlling variable i
var i: Int = 0;

// Execute loop through by array size
while (i < n)
{
if (data[i] < 0 || data[i] > 31)
{
print("\n Limits are Exceeded ", terminator: "");
return;
}
// Left shift of number 1 by array element
location = 1 << data[i];
// Calculate xor of previous result and new bit location
xors = xors ^ location;
i += 1;
}
// Execute loop through by array size n
i = 0;
while (i < n)
{
// Left shift of number 1 by array element
location = 1 << data[i];
if ((location & xors) == 0)
{
print(" ", data[i], terminator: "");
// reset bit position
xors = xors ^ location;
}
i += 1;
}
}
}
func main()
{
// Define array of integer element
let data: [Int] = [7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7];
// Get the size of array
let n: Int = data.count;
}
main();``````

#### Output

``  7  1  5  0``
``````/*
Kotlin program
Find even occurring elements in an array of limited range
Element value between 0 to 31
*/
class Counting
{
fun repeatedEvenTerm(data: Array <Int> , n: Int): Unit
{
// Define some auxiliary resultant variable
var location: Int ;
// This is used to determine number which is occurring Even number of times
var xors: Int = 0;
// Loop controlling variable i
var i: Int = 0;

// Execute loop through by array size
while (i < n)
{
if (data[i] < 0 || data[i] > 31)
{
print("\n Limits are Exceeded ");
return;
}
// Left shift of number 1 by array element
location = 1 shl data[i];
// Calculate xor of previous result and new bit location
xors = xors xor location;
i += 1;
}
// Execute loop through by array size n
i = 0;
while (i < n)
{
// Left shift of number 1 by array element
location = 1 shl data[i];
if ((location and xors) == 0)
{
print(" " + data[i]);
// reset bit position
xors = xors xor location;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
// Define array of integer element
var data: Array <Int> = arrayOf(7, 8, 9, 1, 7, 2, 5, 9, 7, 0, 3, 9, 5, 0, 1, 7);
// Get the size of array
var n: Int = data.count();
}``````

#### Output

`` 7 1 5 0``

## Time Complexity

The time complexity of this algorithm is O(n), where `n` is the number of elements in the array. The algorithm iterates through the array twice, performing constant time operations in each iteration. The overall complexity is linear in terms of the number of elements in the array.

## 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.