Find the Number Occurring Odd Number of Times

Introduction

Dance India Dance has to come to Delhi for auditions. This time the participants will dance in groups. Every group should have an even number of participants. Every group gets a participation number called the Toli number. Sadly, Dharmesh’s team could not find a partner. So, his team tried to trespass on the audition room.

 

Master Remo realized it and tried to find the intruder. Since so many groups came to the auditions, it is impractical to remember all the Toli numbers and find the Toli number with odd frequency. Help the DID crew by writing a code that can solve their problem.

 

Problem Statement

Given an array of numbers ‘ARR’ and its size, find the number which has an odd frequency in the array, given that all other elements have an even frequency. The solution is guaranteed to exist for a given input.

Input Format

Size of the array: 11

Array elements:

0    1    0    2    1    0    1    2    1    2    2

Output Format

Number occurring odd number of times:    0

 

Method 1: Brute Force

One way to find the number with odd frequency is to linearly pick every number and count its number of occurrences in the array. 

Refer to the algorithm given below.

 

Algorithm

  • Loop ‘i’ from 0 to ‘SIZE’ (size of the array)
    • Set COUNTER = 0 (frequency of each element)
    • Loop ‘j’ from 0 to ‘SIZE’
      • If ‘ARR[i]’ equals to ‘ARR[j]’
      • Increment ‘COUNTER’
    • If ‘COUNTER’ is not divisible by 2
      • Return ‘ARR[i]’
  • If no number is returned in the loop
    • Return -1

 

Code for Reference

#include <iostream>
#include <vector>
using namespace std;

// Function to check whether a number is a power of two.
int findOddOccurrence(vector<int> &arr)
{
    int size = arr.size();

    // Loop to traverse the array.
    for (int i = 0; i < size; i++)
    {
        // The 'COUNTER' variable will count the occurrence of element 'ARR[i]'.
        int counter = 0;
        for (int j = 0; j < size; j++)
        {
            // If an element is found, increment the 'COUNTER'.
            if (arr[i] == arr[j])
            {
                counter++;
            }
        }

        // If the element has an odd occurrence, return the element.
        if (counter % 2 == 1)
        {
            return arr[i];
        }
    }

    // If no element with odd occurrence is found, return -1.
    return -1;
}

int main()
{
    // Taking user input.
    cout << "Enter the size of the array: ";
    int n;
    cin >> n;

    vector<int> arr(n);

    cout << "Enter " << n << " elements: ";
    for (int &i : arr)
    {
        cin >> i;
    }

    // Calling findOddOccurrence() function.
    cout << "The element with odd frequency is: " << findOddOccurrence(arr);
    return 0;
}

 

Complexity Analysis

Time complexity: The code uses two nested for loops. The first for loop is used to traverse every element of the array, ‘ARR’. And, for every element, we use a second for loop to compute the frequency,  which takes O(N) time. So, the overall time complexity is O(N * N) = O(N2).

 

Space Complexity: The code does not require any extra space to run. So, the space required is independent of the size of the input given. Space complexity is O(1).

 

Method 2: Hashmaps

Hashmap works in O(1) time complexity for insertion and lookup. So, it can be an easy alternative to the brute force method.  Store the frequency corresponding to each element in a hashmap. Return the element which has an odd frequency.

 

Refer to the algorithm given below for this method.

 

Algorithm

  • Create a hashmap ‘MP’.
  • Iterate through ‘ARR’ using the iterator ‘IT’.
    • If ‘IT’ does not exist as a key in the hashmap
      • Insert ‘IT’ in the hashmap
    • Increment the value of ‘MP[IT]’
  • Iterate through the hashmap ‘MP’.
    • If the iterator value is odd
      • Return iterator key
  • Return -1

 

Code for Reference

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Function to check whether a number is a power of two.
int findOddOccurrence(vector<int> &arr)
{
    int size = arr.size();
    unordered_map<intint> mp;

    // Iteration to store the keys and corresponding frequencies in hashmap.
    for (int &it : arr)
    {
        mp[it]++;
    }

    // Iterating on hashmap to find which of the keys has an odd frequency.
    for (auto it : mp)
    {

        // If the value of the iterator is odd, return the key.
        if (it.second % 2 != 0)
        {
            return it.first;
        }
    }

 

    // If no element with odd occurrence is found, return -1.
    return -1;
}

int main()
{
    // Taking user input.
    cout << "Enter the size of the array: ";
    int n;
    cin >> n;

    vector<int> arr(n);

    cout << "Enter " << n << " elements: ";
    for (int &i : arr) {
        cin >> i;
    }

    // Calling findOddOccurrence() function.
    cout << "The element with odd frequency is: " << findOddOccurrence(arr);
    return 0;
}

 

Complexity Analysis

Time complexity: The code uses two independent for loops. So, the time complexity is O(N + N) = O(N).

 

Space Complexity: As the size of the hashmap depends linearly on the size of the array, the space complexity of the method is O(N).

 

Method 3: Bit Manipulation

Do you remember XOR operations? Don’t worry if you don’t. Here’s a quick revision for the same. Refer to the truth table given below for XOR operations.

 

 

Consider XOR of all elements of the array stored as ‘X’. Elements present in even numbers will not affect the bits of ‘X’. One occurrence unsets the bits set by the other one.

 

Refer to the image given below for a better understanding.

 

 

Neat trick, isn’t it? Refer to the algorithm given below to understand the implementation procedure.

Algorithm

  • Set ANSWER = 0
  • Loop ‘i‘ from 0 to ‘SIZE’ (size of the array)
    • Set ANSWER = ANSWER ^ ARR[I]
  • If ANSWER = 0, return -1 else return ‘ANSWER’

Code for Reference

#include <iostream>
#include <vector>
using namespace std;

// Function to check whether a number is a power of two.
int findOddOccurrence(vector<int> &arr)
{
    int size = arr.size();
    int answer = 0;

    // Loop to iterate through the list.
    for (int i = 0; i < size; i++)
    {

        // Doing bitwise XOR of current element with answer.
        answer = answer ^ arr[i];
    }

    return (answer == 0) ? -1 : answer;
}

int main()
{
    // Taking user input.
    cout << "Enter the size of the array: ";
    int n;
    cin >> n;

    vector<int> arr(n);

    cout << "Enter " << n << " elements: ";
    for (int &i : arr)
    {
        cin >> i;
    }

    // Calling findOddOccurrence() function.
    cout << "The element with odd frequency is: " << findOddOccurrence(arr);
    return 0;
}

 

Complexity Analysis

Time complexity: The code uses a linear loop. So, the time complexity is O(N).

 

Space Complexity: Constant space is used. So, the space complexity is O(1)

 

Key Takeaways

You have successfully learned the methods to solve this problem. Now, you’re all set to help Master Remo. But, don’t just stop your learning here. There is so much more to learn. 

 

Coding Ninjas is here for you to help in your quest for more learning. If you don’t know where to start from, choose one of our guided paths. Listen to your inner voice and head over to  CodeStudio. You can practice top problems, attempt mock tests, read engaging interview experiences, and much more.

Happy Coding!

 

Pranav Gautam

 

Was this article helpful ?
0 upvotes