Find the number which occurs odd number of times

In an array having positive integers, except for one number which occurs odd number of times, all other numbers occur even number of times. Find the number.
Example –
Input : 2 5 9 1 5 1 8 2 8
Output: 9

Input : 2 3 4 3 1 4 5 1 4 2 5
Output: 4

Algorithm

Algorithm 1:
Count the occurrence of each array element and check if it is odd or not. Print the element which has odd occurrence.
This algorithm uses two loops and runs in O(n2) time.

Algorithm 2:
Create a hash map to store the element as key and count of the element as value.
Iterate over the array elements. If the array element is not present in the array, then add the element to the map with count = 1. If the array element is already present because of a previous iteration, then update the count of the array by incrementing the count by 1.
Finally iterate over the map and print the element which has odd occurrence.
This algorithm takes O(n) time and O(n) auxiliary space.

Algorithm 3:
1. Initialize result = input[0].
2. Iterate over the array from i = 1 to length of the array and XOR the result with each element of the input array.
3. Once iteration over the array is done, print result as the output.

XOR operation
Truth Table –


Truth Table of A XOR B shows that it outputs true whenever the input differs.

XOR operation of a number with itself results in 0.
Example:
Consider 5 XOR 5
Binary representation for 5 is 101. Hence applying bitwise XOR on 5 following rules given in the above truth table –
101 XOR 101 = 000 = 0
Now, if XOR is applied on the above result with 5, we get 5 XOR 5 XOR 5 as –
000 XOR 101 = 101 = 5

XOR operation on a number with itself even number of times will result in 0.
XOR operation on a number with itself odd number of times will result in the number itself.
This algorithm takes O(n) time and O(1) auxiliary space.

 

Code->

//C program to find the element occurring odd number of times

#include <stdio.h>
int getOddOccurrence(int ar[], int ar_size)
{
int i;
int res = 0;
for (i=0; i < ar_size; i++)
res = res ^ ar[i];

return res;
}

/* Diver function to test above function */
int main()
{
int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
int n = sizeof(ar)/sizeof(ar[0]);
printf("%d", getOddOccurrence(ar, n));
return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*