Program to Find the Number Occurring Odd Number of Times

  • Write a program to find the an element occurring odd number of times in an array.
  • How to find the only element occurring odd number of times.

Given an array of positive integers, where every element occur even number of times except one element. We have to find an element which occur odd number of times.
For Example :
Input Array : 1, 2, 5, 3, 3, 1, 2
Element occurring odd times : 5

Method 1 : Count the frequency of each element in Array
  • This method used two for loop. Outer for loop will fix one element(let's say K) and inner for loop will count the frequency of K by traversing whole array. After inner for loop ends, we will check if the count of K is odd or even.
  • Time Complexity : O(n2)
Method 2 : Using Hash Table to count frequency of elements.
  • Traverse input array using a for loop. By using array element as key of hash table, store the count of element in hash table. Then traverse the hash table and find element occurring odd number of times.
  • Time Complexity : O(n)
  • Space Complexity : O(n)
Method 3 : Using XOR Bitwise operator.
  • Key point of this algorithm is " XOR of an element even times is 0 and XOR of an element odd times is number itself". For example, A ^ A = 0 whereas A ^ A ^ A = A
  • Traverse input array using a for loop and XOR all elements of array. At the end of traversal, XOR result will host the odd count element of array.
  • Time Complexity : O(n)

C program to find number occurring odd number of times

#include <stdio.h>

int getOddCountElement(int *array, int size) {
     int i, xorResult = 0; 
     /* Take the xor of all array elements */
     for(i = 0; i < size; i++){
      xorResult = xorResult ^ array[i];
  }
     return xorResult;
}

int main(){
 /* This solution assumes that all array 
 elements are positive numbers */
 int array[11] = {4, 3, 7, 5, 1, 3, 5, 3, 1, 3, 4};
 
 printf("Odd Count Element is : %d \n", getOddCountElement(array, 11));

 return 0;
}
Output
Odd Count Element is : 7
Posted by
Labels: ,