Find the Number Occurring Odd Number of Times in an Array

Problem Statement

Given an array of positive integers. All numbers occur even a number of times except one number which occurs an odd number of times. We have to find the number occurring an odd number of times in an array.

Example

Input

1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6

Output

4

Approach 1 for Number Occurring Odd Number of Times

We use the concept of XOR operation to find the number occurring an odd number of times in an array.

As we know,

A xor A = 0    ————- Property 1

i.e. xor of two similar elements is zero.

Also,

A xor 0 = A  —————Property 2

i.e. xor of any element with zero gives the same number.

So our algorithm will be,

Algorithm

1. Start from first element and loop through till the last element of an array. Perform XOR of all elements on an array.

2. XOR from point #1 will be Zero if the number occurs EVEN number of times [by property 1]

3. XOR from point#1 will be equal to the number if it is occurring an odd number of times [by property 2]

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  cin>>a[i];
  //initialize the value as first element
  int val = a[0];
  for(int i=1;i<n;i++)
  {
    //XOR of each element so that we can find the number occurring odd number of times
    val = val^a[i];
  }
  cout<<val<<endl;
  return 0;
}

Java Program

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        //initialize the value as first element
        int val = arr[0];
        for(int i=1;i<n;i++)
        {
          //XOR of each element so that we can find the number occurring odd number of times
          val = val^arr[i];
        }
        System.out.println(val);
    }
}

5
13 5 3 2 1

8

Complexity Analysis for Number Occurring Odd Number of Times

Time Complexity: O(N)

Space Complexity: O(1)

Approach 2 for Number Occurring Odd Number of Times 

Add the elements of an array in a Hash or Map.

Algorithm

1. Add the values in Hash or Map

2. Make an array element as key and the count of elements occurrence as the value of the key.

3. After adding all elements of an array, scan the map’s value and wherever we get a number with the odd count, then that key is the answer.

Implementation

C++ Program 

#include <bits/stdc++.h>
using namespace std;
//map to store 2 int values where first one is for the array element and second one for its count
map<int,int> M;
map<int,int>::iterator it;
int main()
{
  int size;
  cin>>size;
  int arr[size];
  for(int i=0;i<size;i++)
  cin>>arr[i];
  for(int i=0;i<size;i++)
  {
    it = M.find(arr[i]);
    
    // if the number is not present in the map then add it by making its count as 1
    if(it == M.end())
    {
      M.insert(make_pair(arr[i],1));
    }
    else  //if the number is present then simply increase its count by 1
    {
      pair<int,int> p = *it;
      M.erase(it);
      
      //p.second+1 is done for increasing the count by 1
      M.insert(make_pair(p.first,p.second+1));
    }
  }
  
  for(it = M.begin(); it != M.end(); it++)
  {
    //check for odd as if remainder is 1 then if evaluates to true
    if((it->second) % 2 )
    {
      cout<<it->first<<endl;
      return 0;
    }
  }  
  return 0;
}

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++)
        {
            int temp = m.get(arr[i])==null? 1: m.get(arr[i])+1;
            m.put(arr[i], temp);
        }
        for (Integer i : m.keySet()) 
        {
            int x = m.get(i);
            if(x%2==1)
            {
                System.out.println(i);
                return;
            }
        }
    }
}

5
1 2 2 2 1

2

Approach 3 for Number Occurring Odd Number of Times

Last and the most easily thinkable solution is to BRUTE FORCE the entire array.

Algorithm

1. Take an element from the array.

2. Run a loop from the start of array till end and keep on increasing the count whenever we encounter the taken element in point #1.

3. If the count in point#2 is odd then we get the answer or else continue the scan for next elements of an array.

Implementation

C++ Program 

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int size; cin>>size;
  int arr[size];for(int i=0;i<size;i++) cin>>arr[i];
  //select each element as reference
  for(int i=0;i<size;i++)
  {
    int count_of_element = 0;
    for(int j=0;j<size;j++)
    {
      //if the number is same as the reference number
      if(arr[j] == arr[i])
        count_of_element++;
    }
    
    //check for odd as if remainder is 1 then if evaluates to true
    if(count_of_element % 2)
    {
      cout << arr[i] <<endl;
      return 0;
    }
  }
  
  return 0;
}

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        //select each element as reference
        for(int i=0;i<n;i++)
        {
          int count_of_element = 0;
          for(int j=0;j<n;j++)
          {
            //if the number is same as the reference number
            if(arr[j] == arr[i])
              count_of_element++;
          }
          //check for odd as if remainder is 1 then if evaluates to true
          if(count_of_element % 2==1)
          {
            System.out.println(arr[i]);
            return;
          }
        }
    }
}

6
1 2 3 2 1 2

2