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
- The function
repeatedEvenTerm(data, n)
takes an arraydata
of integers and its lengthn
as inputs. - It initializes the
xors
variable to 0, which will be used to find the even occurring elements using bitwise XOR operations. - The first loop iterates through each element in the array.
- For each element, the algorithm checks whether it's within the valid range (0 to 31).
- If the element is within the range, the algorithm calculates the
location
using bitwise left shift operation (1 << data[i]
). - The algorithm performs the XOR operation between the current
xors
value and the calculatedlocation
, updating thexors
value accordingly. - After the first loop, the
xors
value will represent the XOR of elements occurring an odd number of times. - The second loop iterates through each element again.
- For each element, the algorithm checks whether the
location
ANDxors
value is 0. - If the condition is satisfied, it means that the element occurs an even number of times, and it's printed.
- The
xors
value is then updated by performing the XOR operation with the currentlocation
. - 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[0]);
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)
{
Counting task = new Counting();
// 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;
task.repeatedEvenTerm(data, n);
}
}
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()
{
Counting task = Counting();
// 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[0]);
task.repeatedEvenTerm(data, n);
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)
{
Counting task = new Counting();
// 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;
task.repeatedEvenTerm(data, n);
}
}
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()
{
$task = new Counting();
// 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);
$task->repeatedEvenTerm($data, $n);
}
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()
{
var task = new Counting();
// 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;
task.repeatedEvenTerm(data, n);
}
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() :
task = Counting()
# 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)
task.repeatedEvenTerm(data, n)
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()
task = Counting.new()
# 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
task.repeatedEvenTerm(data, n)
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;
task.repeatedEvenTerm(data, n);
}
}
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()
{
let task: Counting = Counting();
// 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;
task.repeatedEvenTerm(data, n);
}
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
{
var task: Counting = Counting();
// 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();
task.repeatedEvenTerm(data, n);
}
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.
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