Do you think IIT Guwahati certified course can help you in your career?
Introduction:
You are given an array of ‘N’ elements in which every element occurs thrice except for one element which occurs only once. We need to find the element that occurs only once.
Let us see a few examples.
Input 1: [1, 2, 3, 2, 1, 5, 1, 2, 5, 5]
Output 1: 2
Explanation 1: All the elements except 2 are present thrice. 2 is present only once.
Input 2: [12, 30, 12, 14, 14, 12, 14]
Output 2: 30
Explanation 2: All the elements except 30 are present thrice. 30 is inkpresent only once.
Approach 1:
We can maintain a map that will store the frequency of each and every element. In the end, we will return the element with a frequency of 1.
Refer to the below implementation of the above approach.
public static int search(int a[], int n)
{
HashMap<Integer, Integer> hm = new HashMap<>();
for(int i = 0;i < n;i++){
hm.put(a[i], hm.getOrDefault(a[i], 0) + 1);
}
for(int val : hm.keySet()){
if(hm.get(val) == 1){
return val;
}
}
return -1;
}
You can also try this code with Online Java Compiler
Time Complexity: The time complexity for the above approach is O(N) where N is the number of elements in the array. We are just iterating the array once and adding the elements to the HashMap which takes O(1) time.
Space Complexity: The space complexity for the above approach is O(N) (where N is the number of elements in the array) because we are pushing all the elements to the HashMap.
Approach 2:
We know that (N - 1) elements appear three times and only one element is present once. From this, we can see that all the bits will have a frequency that is a multiple of three. Few of the bits will not be the multiple of three. Hence, we can include all those bits in our answer which don’t have a frequency that is a multiple of three.
Refer to the below implementation of the above approach.
public static int search(int a[], int n)
{
int ans = 0;
/*
Running a for loop to find
the frequency of all the
32 bits
*/
for(int i = 0; i < 32;i++){
int curBit = (1 << i);
int curFreq = 0;
/*
Running a for loop to
find the frequency of
the current element.
*/
for(int j = 0; j < n; j++){
if((a[j] & curBit) != 0){
curFreq++;
}
}
/*
Checking if the frequency
of the current bit is a
multiple of 3 or not.
*/
if(curFreq % 3 != 0){
ans = (ans | curBit);
}
}
return ans;
}
You can also try this code with Online Java Compiler
Time Complexity: The time complexity for the above approach is O(N * log(N)) where N is the number of elements in the array. We are running a for loop of O(N) time for each bit to count its frequency.
Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space.
Approach 3:
This is a non-trivial solution to this question. We will maintain two things for this approach.
ones: It will contain all the bits that have appeared 1st time or 4th time or 7th time .. etc.
twos: It will contain all the bits that have appeared 2nd time or 5th time or 8th time .. etc.
We just need to return the value of ones in the end.
How to calculate ones and twos?
For each and every new element in the array, find out all the common set bits in new element and the previous value of the ones. These common set bits are the bits that should be added to the twos. So do bitwise XOR of the common set bits with the ‘twos’. The ‘twos’ also gets some extra bits that appear the third time. These extra bits are removed later.
Update ‘ones’ by doing XOR of the new element with the previous value of ‘ones’. There may be some of the bits that appear 3rd time. These extra bits are also removed later.
Both ‘ones’ and ‘twos’ contain those extra bits which appear 3rd time. Remove these extra bits by finding out common set bits in ‘ones’ and ‘twos’.
Refer to the below implementation of the above approach.
static int search(int arr[], int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
for (int i = 0; i < n; i++) {
/*
We are doing (ones & arr[i]) to get the
bits common in both the numbers. We add these
bits to the twos using bitwise OR operator
*/
twos = twos | (ones & arr[i]);
/*
We will XOR the bits of the current element to
ones to get all the bits that appears odd number of times
*/
ones = ones ^ arr[i];
/*
We need to remove all those bits which repeat
third time. Hence, common_bit_mask contains all these
bits as 0, so that these bits are removed from ones
and twos.
*/
common_bit_mask = ~(ones & twos);
/*
Remove common bits (the bits that
appear third time) from 'ones'
*/
ones &= common_bit_mask;
/*
Remove common bits (the bits that
appear third time) from twos
*/
twos &= common_bit_mask;
}
return ones;
}
You can also try this code with Online Java Compiler
Time Complexity: The time complexity for the above approach is O(N) where ‘N’ is the number of elements in the array. We are running a for loop of O(N) time.
Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space.
What is the most optimized approach to solve this problem?
The most optimized approach to solve this problem is using the concept of ones and twos as explained in the 3rd approach.
2. What is the time complexity for the most optimized approach?
The time complexity for the most optimized approach is O(N) where N is the number of elements in the array. We are running a for loop of O(N) time.
Key Takeaways:
In this blog, we have covered the following things:
We discussed the first 2 approaches which everyone should be able to think about.
Then we discussed a no-trivial solution to this problem which was the most optimized.
If you want to learn more about Bit Manipulation and want to practice some questions which require you to take your basic knowledge on Bit Manipulations a notch higher, then you can visit our Guided Path for Bit Manipulation.
Until then, All the best for your future endeavors, and Keep Coding.
34+ registered 
