Skip to main content

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

Last updated on by Kalkicode




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.

New Comment