Do you think IIT Guwahati certified course can help you in your career?
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.
// Function to check whether a number is a power of two. intfindOddOccurrence(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; }
intmain() { // 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); return0; }
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).
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.
// Function to check whether a number is a power of two. intfindOddOccurrence(vector<int> &arr) { int size = arr.size(); unordered_map<int, int> 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; }
intmain() { // 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); return0; }
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.
// Function to check whether a number is a power of two. intfindOddOccurrence(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; }
intmain() { // 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); return0; }
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 Coding Ninjas Studio. You can practice top problems, attempt mock tests, read engaging interview experiences, and much more.
85+ registered