Do you think IIT Guwahati certified course can help you in your career?
Introduction
Mohammed and Ali are two friends who live in Nazaf. Recently they have started to learn programming. One day Ali asked Mohammed a complex problem. He said, given an array, all the elements occur even number of times except two of them. Then he added that I know the brute force approach. But we need to find a solution that takes O(1) space and O(N) time complexity. Mohammed replied that he knows the solution. We need to use Bitwise operators.
Problem Statement
Given an array of size ‘N’, where every element occurs even number of times except two elements which occur odd number of times. Find the elements which occur odd number of times.
The output contains the two elements whose frequency has one. Since 1 and 9 occur one time, thus we print them.
Approach 1
A simple solution that we can think of is iterating the array once for each element and count its frequency. If it occurs an odd number of times, then we print it.
Let’s look at the implementation of this algorithm.
Program
#include <iostream>
#include <vector>
using namespace std;
// Function to find the odd occurring elements in an array.
pair<int, int> findElements(vector<int> &arr)
{
int len = arr.size();
pair<int, int> ans;
int a1, a2;
a1 = a2 = -1;
// Counting frequency of each element
for (int i = 0; i < len; i++)
{
int count = 0;
for (int j = 0; j < len; j++)
{
if (arr[j] == arr[i])
{
count++;
}
}
// If the frequency is odd, we add them in the answer.
if (count % 2 == 1)
{
if (a1 == -1)
{
a1 = arr[i];
}
else
{
a2 = arr[i];
}
}
}
ans = make_pair(a1, a2);
return ans;
}
int main()
{
cout << "Enter the size of the array: ";
int n;
cin >> n;
vector<int> arr(n);
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
pair<int, int> ans = findElements(arr);
cout << "The elements which are occurring odd number of times are: " << ans.first << " and " << ans.second << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Enter the size of the array: 8
Enter 8 elements: 1 1 2 2 3 4 4 6
Output
The elements which are occurring odd number of times are: 3 and 6
Time Complexity
O(N^2), where ‘N’ is the size of the array.
For each element, we traverse the entire array which takes O(N) time for each element. Thus for ‘N’ elements, it will take O(N ^ 2).
Space Complexity
O(1).
As we are not using any extra space here.
Approach 2
We can trade time with space. In the modern era, memory is quite cheap but time is very costly. Time has the power to make you and break you. No one would like a website that takes 10 seconds to load. However, they are ready to allot you as much RAM as you want so that retrieval time is in microseconds.
In this approach, we will use a hashmap to store the frequency of every element. After populating the hashmap, we will traverse it and find the elements which occur an odd number of times. We use hashmaps here because it takes O(1) time for a search and insert. Sounds easy, let’s code it up.
Program
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Function to find the odd occurring elements in an array.
pair<int, int> findElements(vector<int> &arr)
{
int len = arr.size();
pair<int, int> ans;
int a1, a2;
a1 = a2 = -1;
unordered_map<int, int> myMap;
// Storing frequency of each element in a hashmap.
for (int i = 0; i < len; i++)
{
myMap[arr[i]]++;
}
unordered_map<int, int>::iterator it;
// Finding the answer by checking frequency
for (it = myMap.begin(); it != myMap.end(); it++)
{
if (it->second % 2 == 1)
{
if (a1 == -1)
{
a1 = it->first;
}
else
{
a2 = it->first;
}
}
if (a1 != -1 && a2 != -1)
{
break;
}
}
ans = make_pair(a1, a2);
return ans;
}
int main()
{
cout << "Enter the size of the array: ";
int n;
cin >> n;
vector<int> arr(n);
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
pair<int, int> ans = findElements(arr);
cout << "The elements which are occurring odd number of times are: " << ans.first << " and " << ans.second << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Enter the size of the array: 10
Enter 10 elements: 2 4 5 2 9 6 5 6 4 4
Output
The elements which are occurring odd number of times are: 9 and 4
Time Complexity
O(N), where ‘N’ is the size of the array.
The time complexity of this algorithm is O(N). We store each element in a hashtable so that we can access it later in O(1). Thus we iterate the array and find the element’s frequency in O(1). Thus for n elements, it will take O(N) time. Therefore time complexity is O(N).
Space Complexity
O(N), where ‘N’ is the size of the array.
The space complexity of the algorithm is O(N). This is because we are maintaining a hash table to store the frequencies. Thus it occupies O(N) space.
Now, let us discuss the most optimized algorithm, which is efficient in both time and space. We will employ bitwise operators to work upon this algorithm. First, let us visit the function table of XOR for two variables.
A
B
A ^ B
0
0
0
0
1
1
1
0
1
1
1
0
Now if an element occurs an odd number of times then its XOR will eventually become zero. If it occurs 2 * X times, then the number of equal pairs are X and each pair will cancel out to zero. Because A ^ A = 0 from the table. Now the numbers which occur an odd number of times will survive. Let the frequency of the odd element be 2 * X + 1. Then 2* X pairs will cancel each out to zero and one element will sustain. Thus finally we get the XOR of two elements which occurs an odd number of times.
Algorithm
1. First, we find the XOR of the entire array. Let us suppose that the array is [1, 2, 3, 3, 4, 5, 5, 2, 6, 4]. The elements occurring an even number of times will give XOR = 0, and the elements occurring an odd number of times will be XORed.
2. Thus the XOR of the array = 7. Since, 1 ^ 6 = 7. This is the XOR of the two elements but not the element itself. Let them be x and y. Example 1 can be represented as 001 and 6 can be represented as 110. Now, we take 1 ^ 6
001
110
-----
111
And 111=7.
Every set bit in XOR indicates that the corresponding bits in x and y have different values. So, 7(111) indicates that the bits of x and y differ at all three places. Therefore, we select a set bit and divide the array elements into two groups. As a result, both x and y will be assigned to different groups. The rightmost set bit of XOR is chosen in this approach because it is easy to obtain the rightmost set bit of a number. If we XOR all the array elements that have the corresponding bit set (or 1), we get the first odd number. And if we XOR all the elements with the corresponding bit 0, we get the other odd occurring number.
3. Binary Representation of elements of the array are as follows:
Decimal Number
Binary Representation
1
001
2
010
3
011
4
100
5
101
6
110
From the table, we notice that the elements for which the rightmost bit is set are [2, 3, 6] and the elements for which the rightmost bit is not set are [1, 4, 5].
Thus we create our two sets like this.
4. Now, we find the elements in the array whose rightmost bit is set. These elements are [2, 3, 3, 6, 6]. Now when we XOR them we get, x = 010 ^ 011 ^ 011 ^ 110 ^ 110. Elements occurring even number of times will cancel out. Thus x = 2.
5. Now, we find the elements in the array whose rightmost bit is not set. These elements are [1, 1, 4, 5, 5].Now, When we XOR them we get, y = 001 ^ 001 ^ 100 ^ 111 ^ 111. Elements occurring even number of times will cancel out. Thus y = 4.
6. Thus our answer is x = 2 and y = 4.
Let us look at the implementation now.
Program
#include <iostream>
#include <vector>
using namespace std;
// Function to find the odd occurring elements in an array.
pair<int, int> findElements(vector<int> &arr)
{
int n = arr.size();
int temp = 0;
pair<int, int> ans;
// Taking XOR of each element of array.
for (int i = 0; i < n; i++)
{
temp = temp ^ arr[i];
}
int setBit = temp & (~(temp - 1));
int a1 = 0, a2 = 0;
// Finding the answer.
for (int i = 0; i < n; i++)
{
if (arr[i] & setBit)
a1 = a1 ^ arr[i];
else
a2 = a2 ^ arr[i];
}
ans = make_pair(a1, a2);
return ans;
}
int main()
{
cout << "Enter the size of the array: ";
int n;
cin >> n;
vector<int> arr(n);
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
pair<int, int> ans = findElements(arr);
cout << "The elements which are occurring odd number of times are: " << ans.first << " and " << ans.second << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Enter the size of the array: 10
Enter 10 elements: 2 4 5 2 9 6 5 6 4 4
Output
The elements which are occurring odd number of times are: 9 and 4
Time Complexity
O(N), where ‘N’ is the size of the array.
The time complexity of this algorithm is O(N) as we traverse the array twice. First to find the XOR of all the elements and then to find the odd occurring elements.
Space Complexity
O(1).
The space complexity of the algorithm is O(1) as we are not using any extra space. We are just declaring a handful of variables.
Key Takeaways
In this blog, we learned about a famous interview problem, Find Elements. We discussed three approaches to solve the problem. The first approach is counting frequencies using a nested loop which gives time complexity of O(N ^ 2). Next, we used hashmaps to store the frequencies which reduced the time complexity to O(N). But it took O(N) space too. Finally, we saw the most optimized approach using Bitwise operators, which gave the time complexity of O(N) and space complexity of O(1). You can consider checking out our DSA Course which has helped plenty of students to get placed in top product-based companies.
136+ registered 
