Find the element that appears once in an array

Find the element that appears only once in a given set of integers while all the other elements occur N times.

Algorithm 1:
1: Create countSetBits[] array of size 32(for representing 32 bit integer) where,
countSetBits[i] represents count of ith set bit of all elements in the input array.
Initially all elements of countSetBits[] array are 0.
2: Traverse all the elements of the input array to populate countSetBits, by doing step #3 for each of them.
3: Take the element and check for its set bits. If the ith bit is found to be set, then in the countSetBits[] array increment the count of the element at the index 'i'.
4: After finishing the above operation for all the elements of the input array, the elements of countSetBits[] would represent count of all set bits in the elements of input array.
Perform the modulus N operation on each element of the countSetBits[] array.
Modules N operation will eliminate count of set bits of elements occurring N times.
After the modulus N operation, if we get a remainder 1 at an index 'j', then that means in the number that occurs only once, we have a set bit at index 'j'.
After the modulus N operation on each element, the countSetBits[] array represents bits representation of required element. Set individual bits in variable ‘solution’.

Time Complexity: O(n)
Space Complexity: O(1)

Algorithm 2:
1: Initialize solution = 0.
2: Set individual bits of ‘solution’ by doing step #3.
3: To set ith bit position of ‘solution’, calculate sum of all of ith set bit of all elements in the input array, and mod it by N.

Time Complexity: O(n)
Space Complexity: O(1)

Code and Algorithm Visualization:

[naveenmarikar]

Thanks for this! Never understood this bit set array before until now.

[namitarane]

The visualization helped a lot. Thank you!

[GauravGupta-zwhz]

Thanks, man for the awesome explanation. Just came across your channel recently.

[PRADHYUMNGANGWAR]

Superb explanation man .... Was able to get it in one go ;)

[falakk]

Superb Thanks for such a bright explanation . You deserve all appreciations .

[FusionX]

The way I understand the first solution is, and I do not know at all if I'm wrong.

First, know the properties of XOR:
1. Any number XOR with itself is 0.
2. Any number XOR with 0 is the number itself.
3. XOR is commutative and associative (read up on google)

Now, remember this, XOR is also known as addition modulus 2, i.e. 3 (11 in binary) XOR 2 (10 in binary) can also be solved by adding each bit of both numbers and doing modulus 2,
1 1
+ +
1 0


2 1 (I added bits in binary and represented it in decimal for ease of understanding, it's the same result if you do it in binary)
%2 %2

0 1


Which is the result of 3 XOR 2..


Now, Suppose N=2, 4, 6, ...
This is the case of normal XOR which you can find on GeeksforGeeks. These are multiple of 2, so any number that appears even times gets canceled with XOR operation (because number XOR itself is 0).

As for N=3, 5, 7..
Now we cannot apply XOR since N is not multiple of 2 so it won't work. Instead what we can do is use the underlying concept behind XOR that is addition 2 modulus and modify it to addition modulus N.
So, in the algorithm, you add all the bits of the numbers at their respective places (addition)
And then you do a modulus N for each individual added bit, as I explained before. (modulus N)
Therefore any number that appears N times gets canceled, similar to XOR.


Finally, what you're left with is the unique element that appears once.

I'm not good at explaining but I tried, do a bit of googling and see geeksforgeeks solution and it should make some sense.

[AP-ehgr]

hey excellent work explaining these small but significant questions!

[viralfromindia]

@IDeserve - Why the space complexity is O(1). The size of countSetBit array depends on the size of input array, so shouldn't the space complexity also be O(N)?

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[IDeserve]

+Naveen Marikar

Thanks Naveen :)
We are striving hard to make understanding algorithms easier.

We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues.

It has features like algorithm visualizations, learn together and many more coming soon.
Please check it out and leave us a comment there!

Thanks,
-Team IDeserve.

[selvalooks]

amazed !!! wonderful !!! solution 2 was damn simple solution and understandable !!!

[douggynix]

If you use a dictionnary like a Hashmap table, and add each value in the hashmap as key and value. The key would be the array value, and once getting the key, it would be initialized with count of keys already visited or a boolean value(true or false).
At the end, we would scan the hashmap for the key that has false or count=1. If found, this would be the single element repeated once in the array.
Hashmap would be lesser than the array length by using array value as index. and the loop to search for keys would be quicker.
What do you think?

By the way, i like the solution you proposed, it is a very smart one with bitwise approach. However, this would not be a straightforward approach for one to solve this problem at first sight :).

[RAVIKUMAR-efwo]

excellent explanation...thank you very much

[KrishMunot]

In this particular case, N is given as 3 (all elements repeat thrice except one), what if the elements repeat multiple times and N is not given. How would you solve that problem then?

[terigopula]

10/10 for the sound and narration quality. It would have been awesome if also explained the intuition behind %n. XOR kinda exploits %2 and gives a solution for single element where rest are repeating twice. We simply generalized the XOR idea for numbers repeating 'n' times instead of twice.

[malharjajoo]

if anyone wants working code -

// NOTE - All other slements must repeat exactly "N" times ( N may be even or odd )
int findSingularElement(int A[], int sizeA, int N)
{
int maxElement = A[0] ;
for(int i =0; i < sizeA ;i++)
{
if(A[i]> maxElement)
{
maxElement = A[i] ;
}
}

int res = 0 ;
int exp = 1 ;
// O(nlogn)

for(int k=1;k <= maxElement ;k*=2)
{
int sum = 0 ;
for(int j = 0 ; j < sizeA ;j++)
{
sum+= ((A[j]&k)>0);
}


int bitval = sum%N; // find bit of the solution
cout << "bitval = " << bitval << endl ;

res+= (bitval*k);




}

return res;

}

int main()
{


int A[] = {5, 5, 4, 8, 4, 5, 8, 9, 4, 8};

cout << findSingularElement(A, 10, 3);


}

[vijayendrasdm]

good explanation

please do a video for
K'th largest element in a stream [ different approaches ]
Median in a stream of integers (running integers) [different approaches]

[twrkhanasparukh]

this is Time O(w*n) and Space O(w), where w is word size (bit lenngth)

[aprofromuk]

probably shud mention for n = 2, just XOR the elements for an easy solution :)

Also space complexity is O(n), where n is the number of bits.

[infinity_shows_]

Awesome explanation sir....keep on your outstanding work..best wishes...:)