Find Odd Occurrence Element
You are given an array of 'N' elements. In this given array, each element appears an even number of times except one element which appears odd no. of times. Your task is to find the element which occurs an odd number of times.

For example :

Input array [5,5,6,4,6],If we look at the frequency of different elements in this array.We can see,4 appears an odd number of times, so our answer will be 4.

Input Format :

The first line of input contains a single integer 'T', representing the number of test cases. Then the 'T' test cases follow. The first line of each test case contains a number 'N' denoting the size of the array. The second line contains 'N' space-separated distinct integers denoting elements of the array.

Output format :

For each test case print the element which appears an odd number of times. The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Find Odd Occurrence Element

You are given an array of 'N' elements. In this given array, each element appears an even number of times except one element which appears odd no. of times. Your task is to find the element which occurs an odd number of times.

For example :

Input array [5,5,6,4,6],If we look at the frequency of different elements in this array.We can see,4 appears an odd number of times, so our answer will be 4.

Input Format :

The first line of input contains a single integer 'T', representing the number of test cases.
Then the 'T' test cases follow.

The first line of each test case contains a number 'N' denoting the size of the array.
The second line contains 'N' space-separated distinct integers denoting elements of the array.

Output format :

For each test case print the element which appears an odd number of times.

The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1<= T <=100
1 <= N <= 10000
1 <= ARR[i] <= 10^8

Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, and 'ARR[i]' denotes the 'i'th' element of the array 'ARR'.

Time limit : 1 sec

Accepted Answer

Brute force

We will find the frequency of all elements by iterating over the whole array N times. On completion of iteration if the frequency of element is odd. We will return this element else keep on iterating.

Let’s say we have a given array ARR and pair sum K.
Iterate over ARR[i] for each 0 <= i < N and do:
1. COUNT=0
2. Iterate over ARR[j] for each 0 <= j < N and do:
  1. If ARR[i] = ARR[j] then increase COUNT by 1.
3. If COUNT is odd then return ARR[i].

Space Complexity: O(1)Explanation:

O(1).

Constant memory is being used. Hence, the overall space complexity is O(1).

Time Complexity: O(n^2)Explanation:

O(N^2) where N is the length of the string.

We are iterating over the whole array for each element. So for N elements, the overall time complexity is O(N^2).

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where N is the number of elements in array

*/



int findOdd(int *arr,int n)

{

    for(int i=0;i    {	

        // Variable to count frequency

        int count=0; 

        

        // Traverse through the array

        for(int j=0;j        {

            if(arr[i]==arr[j])

            {

                count+=1;

            }

        }

        

        // Check if frequency is odd

        if(count%2!=0)

        {

            return arr[i];

        }

    }

}

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where N is the number of elements in array

*/



public class Solution 

{

	public static int findOdd(int[] arr, int n) 

    {

		for (int i = 0; i < n; i++) 

        {	

            // Variable to count frequency`

			int count = 0;

			

            // Traverse through the array

            for (int j = 0; j < n; j++) 

            {

				if (arr[i] == arr[j]) 

                {

					count += 1;

				}

			}

           

            // Check if frequency is odd

			if (count % 2 != 0) 

            {

				return arr[i];

			}

		}

        

		return -1;

	}



}

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where N is the number of elements in array

'''



def findOdd(arr, n):



    for i in range(n):



        # Variable to count frequency 

        count = 0

        

        # Traverse through the array

        for j in range(n):



            if(arr[i] == arr[j]):

                count += 1



        # Check if frequency is odd

        if(count % 2 != 0):

            return arr[i]

Accepted Answer

Hashing Technique

We will scan the array from left to right and we will use the Hash to store frequency of each element. On encountering an element we will increase its hash value by 1.No we will scan again and check the Hash value of each element and we can find the element with odd frequency.

Let's say we have given an array ARR.
We are using an unordered_map called MYMAP as Hash.
Iterate over ARR[i] for each 0 <= i < N and do:
1. MYMAP[ARR[i]] += 1
Iterate over ARR[i] for each 0 <= i < N and do:
1. If MYMAP[ARR[i]] is odd then return ARR[i]

Space Complexity: O(n)Explanation:

O(N), where N is the length of the string.

We are using the map to store N elements that take O(N) space complexity. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the length of the string.

We are iterating over the array of length N that takes O(N) time and the time complexity of accessing the map is O(1). Hence, the overall time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of elements in array

*/



import java.util.HashMap;



public class Solution 

{

	public static int findOdd(int[] arr, int n) 

    {	

        // HashMap to store frequency of each element

		HashMap myMap = new HashMap<>();

		

        // Traverse through the array

		for (int i = 0; i < n; i++) 

        {

			if (myMap.containsKey(arr[i])) 

            {

				int val = myMap.get(arr[i]);

				myMap.put(arr[i], val + 1);

			} 

            else 

            {

				myMap.put(arr[i], 1);

			}

		}

		

        // Traverse through the HashMap

		for (Integer a : myMap.keySet()) 

        {	

            // Check if frequency is odd

			if (myMap.get(a) % 2 != 0) 

            {

				return a;

			}

		}

		

		return -1;

	}

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of elements in array

'''



def findOdd(arr, n):



    # HashMap to store frequency of each element

    myMap = {}



    # Traverse through the array

    for i in range(n):



        if(arr[i] in myMap):

            myMap[arr[i]] = myMap[arr[i]] + 1

            

        else:

            myMap[arr[i]] = 1



    # Traverse through the HashMap

    for it in myMap:



        element = it

        freq = myMap[it]



        # Check if frequency is odd

        if(freq % 2 != 0):

            return element

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of elements in array

*/



#include



int findOdd(int *arr,int n)

{

    // HashMap to store frequency of each element

    unordered_map myMap;

	

    // Traverse through the array

    for(int i = 0; i < n; i++)

    {

        myMap[arr[i]] += 1;

    }

    

    // Traverse through the HashMap

    for(auto it : myMap)

    {

        int element = it.first;

        int freq = it.second;

		

        // Check if frequency is odd

        if(freq % 2 != 0) 

        {

            return element;

        }

    }

}

Accepted Answer

XOR

As XOR value of two same elements is zero and XOR of any element, say X, with 0 is X.We can use this fact in our problem, as if we XOR all elements of the array, then elements which appear even no. of time will always add 0 to result. So the result will have only one element which appears odd no. of time.

Algorithm :

Initialize an integer variable RESULT=0
Let's say we have given an array ARR.
Iterate over ARR[i] for each 0 <= i < N and do:
1. RESULT = RESULT ^ ARR[i] (where ^ is XOR operator)
Return RESULT.

Space Complexity: O(1)Explanation:

O(1).

Constant memory is being used. Hence, the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the length of the string.

We are iterating over the array of length N that takes O(N) time. Hence, the overall time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the number of elements in array

*/



public class Solution 

{

	public static int findOdd(int[] arr, int n) 

    {

		int result = 0;

		

        // Iterating over array and taking XOR

        for (int i = 0; i < n; i++) 

        {

			result = result ^ arr[i];

		}

		

        // Return the variable result

        return result;

	}

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the number of elements in array

'''



def findOdd(arr, n):



    result=0



    # Iterating over array and taking XOR

    for i in range(n):

        result = result^arr[i]



    # Return the variable result

    return result

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the number of elements in array

*/



int findOdd(int *arr,int n)

{

    int result=0;

    

    // Iterating over array and taking XOR

    for(int i=0;i    {

        result = result^arr[i];

    }

    

    // Return the variable result

    return result;

}

You are given an array of 'N' elements. In this given array, each element appears an even number of times except one element which appears odd no. of times. Your task is to find the element which occurs an odd number of times.

For example :

Input Format :

Output format :

Note :

Constraints :

Top Jupiter Money Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern